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

The bi-objective mixed capacitated general routing problem with different route balance criteria

Author

Listed:
  • Halvorsen-Weare, Elin E.
  • Savelsbergh, Martin W.P.

Abstract

In the mixed capacitated general routing problem, one seeks to determine a minimum cost set of vehicle routes serving segments of a mixed network consisting of nodes, edges, and arcs. We study a bi-objective variant of the problem, in which, in addition to seeking a set of routes of low cost, one simultaneously seeks a set of routes in which the work load is balanced. Due to the conflict between the objectives, finding a solution that simultaneously optimizes both objectives is usually impossible. Thus, we seek to generate many or all efficient, or Pareto-optimal, solutions, i.e., solutions in which it is impossible to improve the value of one objective without deterioration in the value of the other objective. Route balance can be modeled in different ways, and a computational study using small benchmark instances of the mixed capacitated general routing problem demonstrates that the choice of route balance modeling has a significant impact on the number and diversity of Pareto-optimal solutions. The results of the computational study suggest that modeling route balance in terms of the difference between the longest and shortest route in a solution is a robust choice that performs well across a variety of instances.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:ejores:v:251:y:2016:i:2:p:451-465
    DOI: 10.1016/j.ejor.2015.11.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715010735
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2015.11.024?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. 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.
    2. 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.
    3. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    4. A Corberán & E Fernández & M Laguna & R Martí, 2002. "Heuristic solutions to the problem of routing school buses with multiple objectives," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(4), pages 427-435, April.
    5. Martínez-Salazar, Iris Abril & Molina, Julian & Ángel-Bello, Francisco & Gómez, Trinidad & Caballero, Rafael, 2014. "Solving a bi-objective Transportation Location Routing Problem by metaheuristic algorithms," European Journal of Operational Research, Elsevier, vol. 234(1), pages 25-36.
    6. Beraldi, Patrizia & Bruni, Maria Elena & Laganà, Demetrio & Musmanno, Roberto, 2015. "The mixed capacitated general routing problem under uncertainty," European Journal of Operational Research, Elsevier, vol. 240(2), pages 382-392.
    7. Peter Reiter & Walter Gutjahr, 2012. "Exact hybrid algorithms for solving a bi-objective 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. 20(1), pages 19-43, March.
    8. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "The bi-objective Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 464-478.
    9. 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.
    10. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    11. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 735-754, November.
    12. Rita Ribeiro & Helena Ramalhinho-Lourenço, 2001. "A multi-objective model for a multi-period distribution management problem," Economics Working Papers 532, Department of Economics and Business, Universitat Pompeu Fabra.
    13. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 597-618, November.
    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. 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.
    2. 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.
    3. Pourhejazy, Pourya & Zhang, Dali & Zhu, Qinghua & Wei, Fangfang & Song, Shuang, 2021. "Integrated E-waste transportation using capacitated general routing problem with time-window," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    4. Martha-Selene Casas-Ramírez & José-Fernando Camacho-Vallejo & Rosa G. González-Ramírez & José-Antonio Marmolejo-Saucedo & José-Manuel Velarde-Cantú, 2018. "Optimizing a Biobjective Production-Distribution Planning Problem Using a GRASP," Complexity, Hindawi, vol. 2018, pages 1-13, February.
    5. 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).
    6. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    7. 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.
    8. Francesco Pilati & Riccardo Tronconi, 2024. "Tri-Objective Vehicle Routing Problem to Optimize the Distribution Process of Sustainable Local E-Commerce Platforms," Sustainability, MDPI, vol. 16(5), pages 1-36, February.

    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. 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.
    2. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    3. Xiaopan Chen & Yunfeng Kong & Lanxue Dang & Yane Hou & Xinyue Ye, 2015. "Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-20, July.
    4. Jasmin Grabenschweiger & Fabien Tricoire & Karl F. Doerner, 2018. "Finding the trade-off between emissions and disturbance in an urban context," Flexible Services and Manufacturing Journal, Springer, vol. 30(3), pages 554-591, September.
    5. Miriam Enzi & Sophie N. Parragh & Jakob Puchinger, 2022. "The bi-objective multimodal car-sharing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 307-348, June.
    6. 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.
    7. Chen, Xinwei & Wang, Tong & Thomas, Barrett W. & Ulmer, Marlin W., 2023. "Same-day delivery with fair customer service," European Journal of Operational Research, Elsevier, vol. 308(2), pages 738-751.
    8. Hernan Caceres & Rajan Batta & Qing He, 2017. "School Bus Routing with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 51(4), pages 1349-1364, November.
    9. Yu, Yang & Wu, Yuting & Wang, Junwei, 2019. "Bi-objective green ride-sharing problem: Model and exact method," International Journal of Production Economics, Elsevier, vol. 208(C), pages 472-482.
    10. 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.
    11. Joaquín Pacheco & Rafael Caballero & Manuel Laguna & Julián Molina, 2013. "Bi-Objective Bus Routing: An Application to School Buses in Rural Areas," Transportation Science, INFORMS, vol. 47(3), pages 397-411, August.
    12. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.
    13. Atashpaz Gargari, Masoud & Sahraeian, Rashed, 2023. "An exact criterion space search method for a bi-objective nursing home location and allocation problem," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 206(C), pages 166-180.
    14. Yıldız, Gazi Bilal & Soylu, Banu, 2019. "A multiobjective post-sales guarantee and repair services network design problem," International Journal of Production Economics, Elsevier, vol. 216(C), pages 305-320.
    15. Ohad Eisenhandler & Michal Tzur, 2019. "The Humanitarian Pickup and Distribution Problem," Operations Research, INFORMS, vol. 67(1), pages 10-32, January.
    16. Fattahi, Ali & Turkay, Metin, 2018. "A one direction search method to find the exact nondominated frontier of biobjective mixed-binary linear programming problems," European Journal of Operational Research, Elsevier, vol. 266(2), pages 415-425.
    17. Masar Al-Rabeeah & Santosh Kumar & Ali Al-Hasani & Elias Munapo & Andrew Eberhard, 2019. "Bi-objective integer programming analysis based on the characteristic equation," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 10(5), pages 937-944, October.
    18. Soylu, Banu & Katip, Hatice, 2019. "A multiobjective hub-airport location problem for an airline network design," European Journal of Operational Research, Elsevier, vol. 277(2), pages 412-425.
    19. Seyyed Amir Babak Rasmi & Ali Fattahi & Metin Türkay, 2021. "SASS: slicing with adaptive steps search method for finding the non-dominated points of tri-objective mixed-integer linear programming problems," Annals of Operations Research, Springer, vol. 296(1), pages 841-876, January.
    20. Hongming Li & Xintao Li, 2022. "A Branch-and-Bound Algorithm for the Bi-Objective Quay Crane Scheduling Problem Based on Efficiency and Energy," Mathematics, MDPI, vol. 10(24), pages 1-20, December.

    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:251:y:2016:i:2:p:451-465. 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.