IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v282y2020i1p129-147.html
   My bibliography  Save this article

A lexicographic minimax approach to the vehicle routing problem with route balancing

Author

Listed:
  • Lehuédé, Fabien
  • Péton, Olivier
  • Tricoire, Fabien

Abstract

Vehicle routing problems generally aim at designing routes that minimize transportation costs. However, in practical settings, many companies also pay attention at how the workload is distributed among its drivers. Accordingly, two main approaches for balancing the workload have been proposed in the literature. They are based on minimizing the duration of the longest route, or the difference between the longest and the shortest routes, respectively. Recently, it has been shown on several occasions that both approaches have some flaws. In order to model equity we investigate the lexicographic minimax approach, which is rooted in social choice theory. We define the leximax vehicle routing problem which considers the bi-objective optimization of transportation costs and of workload balancing. This problem is solved by a heuristic based on the multi-directional local search framework. It involves dedicated large neighborhood search operators. Several LNS operators are proposed and compared in experimentations.

Suggested Citation

  • Lehuédé, Fabien & Péton, Olivier & Tricoire, Fabien, 2020. "A lexicographic minimax approach to the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 282(1), pages 129-147.
    • Handle: RePEc:eee:ejores:v:282:y:2020:i:1:p:129-147
    DOI: 10.1016/j.ejor.2019.09.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719307489
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.09.010?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Liu, Songsong & Papageorgiou, Lazaros G., 2013. "Multiobjective optimisation of production, distribution and capacity planning of global supply chains in the process industry," Omega, Elsevier, vol. 41(2), pages 369-382.
    2. Wlodzimierz Ogryczak & Hanan Luss & Michał Pióro & Dritan Nace & Artur Tomaszewski, 2014. "Fair Optimization and Networks: A Survey," Journal of Applied Mathematics, Hindawi, vol. 2014, pages 1-25, September.
    3. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    4. Herve Moulin, 2004. "Fair Division and Collective Welfare," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262633116, April.
    5. István Borgulya, 2008. "An algorithm for the capacitated vehicle routing problem with route balancing," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 16(4), pages 331-343, December.
    6. Sleman Saliba, 2006. "Heuristics for the lexicographic max-ordering vehicle routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 14(3), pages 313-336, September.
    7. David Pisinger & Stefan Ropke, 2019. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, edition 3, chapter 0, pages 99-127, Springer.
    8. Dimitris Bertsimas & Vivek F. Farias & Nikolaos Trichakis, 2011. "The Price of Fairness," Operations Research, INFORMS, vol. 59(1), pages 17-31, February.
    9. Jozefowiez, Nicolas & Semet, Frédéric & Talbi, El-Ghazali, 2009. "An evolutionary algorithm for the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 195(3), pages 761-769, June.
    10. Alois Behringer, Fred, 1981. "A simplex based algorithm for the lexicographically extended linear maxmin problem," European Journal of Operational Research, Elsevier, vol. 7(3), pages 274-283, July.
    11. Halvorsen-Weare, Elin E. & Savelsbergh, Martin W.P., 2016. "The bi-objective mixed capacitated general routing problem with different route balance criteria," European Journal of Operational Research, Elsevier, vol. 251(2), pages 451-465.
    12. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    13. Hanan Luss, 2010. "Equitable bandwidth allocation in content distribution networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(3), pages 266-278, April.
    14. Bertazzi, Luca & Golden, Bruce & Wang, Xingyin, 2015. "Min–Max vs. Min–Sum Vehicle Routing: A worst-case analysis," European Journal of Operational Research, Elsevier, vol. 240(2), pages 372-381.
    15. Dritan Nace & James B. Orlin, 2007. "Lexicographically Minimum and Maximum Load Linear Programming Problems," Operations Research, INFORMS, vol. 55(1), pages 182-187, February.
    16. Ogryczak, Wlodzimierz, 1997. "On the lexicographic minimax approach to location problems," European Journal of Operational Research, Elsevier, vol. 100(3), pages 566-585, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dukkanci, Okan & Karsu, Özlem & Kara, Bahar Y., 2022. "Planning sustainable routes: Economic, environmental and welfare concerns," European Journal of Operational Research, Elsevier, vol. 301(1), pages 110-123.
    2. Marie-Sklaerder Vié & Nicolas Zufferey & Roel Leus, 2022. "Aircraft landing planning under uncertain conditions," Journal of Scheduling, Springer, vol. 25(2), pages 203-228, April.
    3. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    4. Jian Zhou & Meixi Zhang & Sisi Wu, 2022. "Multi-Objective Vehicle Routing Problem for Waste Classification and Collection with Sustainable Concerns: The Case of Shanghai City," Sustainability, MDPI, vol. 14(18), pages 1-25, September.
    5. He, Pengfei & Hao, Jin-Kao, 2023. "Memetic search for the minmax multiple traveling salesman problem with single and multiple depots," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1055-1070.
    6. Hua, Mingzhuang & Chen, Xuewu & Chen, Jingxu & Huang, Di & Cheng, Long, 2022. "Large-scale dockless bike sharing repositioning considering future usage and workload balance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    7. Mohammadmehdi Hakimifar & Vera C. Hemmelmayr & Fabien Tricoire, 2022. "A Bi-Objective Field-Visit Planning Problem for Rapid Needs Assessment under Travel-Time Uncertainty," Sustainability, MDPI, vol. 14(5), pages 1-16, March.
    8. Mohammadmehdi Hakimifar & Vera C. Hemmelmayr & Fabien Tricoire, 2023. "A lexicographic maximin approach to the selective assessment routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(1), pages 205-249, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mohammadmehdi Hakimifar & Vera C. Hemmelmayr & Fabien Tricoire, 2022. "A Bi-Objective Field-Visit Planning Problem for Rapid Needs Assessment under Travel-Time Uncertainty," Sustainability, MDPI, vol. 14(5), pages 1-16, March.
    2. P. Matl & R. F. Hartl & T. Vidal, 2018. "Workload Equity in Vehicle Routing Problems: A Survey and Analysis," Transportation Science, INFORMS, vol. 52(2), pages 239-260, March.
    3. Mohammadmehdi Hakimifar & Vera C. Hemmelmayr & Fabien Tricoire, 2023. "A lexicographic maximin approach to the selective assessment routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(1), pages 205-249, March.
    4. Dukkanci, Okan & Karsu, Özlem & Kara, Bahar Y., 2022. "Planning sustainable routes: Economic, environmental and welfare concerns," European Journal of Operational Research, Elsevier, vol. 301(1), pages 110-123.
    5. Liu, Songsong & Papageorgiou, Lazaros G., 2018. "Fair profit distribution in multi-echelon supply chains via transfer prices," Omega, Elsevier, vol. 80(C), pages 77-94.
    6. Christ, Quentin & Dauzère-Pérès, Stéphane & Lepelletier, Guillaume, 2019. "An Iterated Min–Max procedure for practical workload balancing on non-identical parallel machines in manufacturing systems," European Journal of Operational Research, Elsevier, vol. 279(2), pages 419-428.
    7. Ohad Eisenhandler & Michal Tzur, 2019. "The Humanitarian Pickup and Distribution Problem," Operations Research, INFORMS, vol. 67(1), pages 10-32, January.
    8. Halvorsen-Weare, Elin E. & Savelsbergh, Martin W.P., 2016. "The bi-objective mixed capacitated general routing problem with different route balance criteria," European Journal of Operational Research, Elsevier, vol. 251(2), pages 451-465.
    9. Argyris, Nikolaos & Karsu, Özlem & Yavuz, Mirel, 2022. "Fair resource allocation: Using welfare-based dominance constraints," European Journal of Operational Research, Elsevier, vol. 297(2), pages 560-578.
    10. Gutjahr, Walter J., 2021. "Inequity-averse stochastic decision processes," European Journal of Operational Research, Elsevier, vol. 288(1), pages 258-270.
    11. Chen, Qingxin & Fu, Chenyi & Zhu, Ning & Ma, Shoufeng & He, Qiao-Chu, 2023. "A target-based optimization model for bike-sharing systems: From the perspective of service efficiency and equity," Transportation Research Part B: Methodological, Elsevier, vol. 167(C), pages 235-260.
    12. El Mehdi, Er Raqabi & Ilyas, Himmich & Nizar, El Hachemi & Issmaïl, El Hallaoui & François, Soumis, 2023. "Incremental LNS framework for integrated production, inventory, and vessel scheduling: Application to a global supply chain," Omega, Elsevier, vol. 116(C).
    13. David Rea & Craig Froehle & Suzanne Masterson & Brian Stettler & Gregory Fermann & Arthur Pancioli, 2021. "Unequal but Fair: Incorporating Distributive Justice in Operational Allocation Models," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2304-2320, July.
    14. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    15. Chen, Violet Xinying & Hooker, J.N., 2022. "Combining leximax fairness and efficiency in a mathematical programming model," European Journal of Operational Research, Elsevier, vol. 299(1), pages 235-248.
    16. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    17. Agnetis, Alessandro & Chen, Bo & Nicosia, Gaia & Pacifici, Andrea, 2019. "Price of fairness in two-agent single-machine scheduling problems," European Journal of Operational Research, Elsevier, vol. 276(1), pages 79-87.
    18. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.
    19. J. N. Hooker & H. P. Williams, 2012. "Combining Equity and Utilitarianism in a Mathematical Programming Model," Management Science, INFORMS, vol. 58(9), pages 1682-1693, September.
    20. Tom Demeulemeester & Dries Goossens & Ben Hermans & Roel Leus, 2023. "Fair integer programming under dichotomous and cardinal preferences," Papers 2306.13383, arXiv.org, revised Apr 2024.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:282:y:2020:i:1:p:129-147. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.