IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v42y2020i1d10.1007_s00291-019-00570-z.html
   My bibliography  Save this article

A matheuristic for the swap body vehicle routing problem

Author

Listed:
  • Sandra Huber

    (Helmut Schmidt University
    HEC Montréal)

  • Jean-François Cordeau

    (HEC Montréal)

  • Martin Josef Geiger

    (Helmut Schmidt University)

Abstract

We consider the swap body vehicle routing problem, an extension of the capacitated vehicle routing problem, in which intermediate locations can be used to change the configuration of a vehicle. Possible actions include a parking operation that decouples the semitrailer as well as a swapping operation that switches the swap body with another one, which was previously parked at an intermediate location. Successful ideas that combine mathematical programming and heuristics have been recently presented for several vehicle routing problems. In this line, the contribution of this paper is the development of a column generation-based approach, in which a variable neighborhood search heuristic populates the route pool. A detailed numerical analysis is carried out for 138 instances with up to 1000 customers and at most 100 intermediate locations. Comparisons with existing metaheuristics show that our solution strategy is suitable for solving this problem. It has obtained 42 new best known solutions with a maximal improvement of 18.54% on published benchmark instances.

Suggested Citation

  • Sandra Huber & Jean-François Cordeau & Martin Josef Geiger, 2020. "A matheuristic for the swap body vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 111-160, March.
    • Handle: RePEc:spr:orspec:v:42:y:2020:i:1:d:10.1007_s00291-019-00570-z
    DOI: 10.1007/s00291-019-00570-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-019-00570-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00291-019-00570-z?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. Gunes Erdogan & Fraser McLeod & Tom Cherrett & Tolga Bektas, 2015. "Matheuristics for solving a multi-attribute collection problem for a charity organisation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(2), pages 177-190, February.
    2. Juan José Miranda-Bront & Brian Curcio & Isabel Méndez-Díaz & Agustín Montero & Federico Pousa & Paula Zabala, 2017. "A cluster-first route-second approach for the swap body vehicle routing problem," Annals of Operations Research, Springer, vol. 253(2), pages 935-956, June.
    3. Huber, Sandra & Geiger, Martin Josef, 2017. "Order matters – A Variable Neighborhood Search for the Swap-Body Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 263(2), pages 419-445.
    4. Kramer, Raphael & Subramanian, Anand & Vidal, Thibaut & Cabral, Lucídio dos Anjos F., 2015. "A matheuristic approach for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 243(2), pages 523-539.
    5. Jorge E. Mendoza & Louis-Martin Rousseau & Juan G. Villegas, 2016. "A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints," Journal of Heuristics, Springer, vol. 22(4), pages 539-566, August.
    6. Subramanian, Anand & Penna, Puca Huachi Vaz & Uchoa, Eduardo & Ochi, Luiz Satoru, 2012. "A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 221(2), pages 285-295.
    7. Z Wang & W Liang & X Hu, 2014. "A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(1), pages 37-48, January.
    8. Uchoa, Eduardo & Pecin, Diego & Pessoa, Artur & Poggi, Marcus & Vidal, Thibaut & Subramanian, Anand, 2017. "New benchmark instances for the Capacitated Vehicle Routing Problem," European Journal of Operational Research, Elsevier, vol. 257(3), pages 845-858.
    Full references (including those not matched with items on IDEAS)

    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. Pessoa, Artur & Sadykov, Ruslan & Uchoa, Eduardo, 2018. "Enhanced Branch-Cut-and-Price algorithm for heterogeneous fleet vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 270(2), pages 530-543.
    2. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    3. Mikhail V. Batsyn & Ekaterina K. Batsyna & Ilya S. Bychkov & Panos M. Pardalos, 2021. "Vehicle assignment in site-dependent vehicle routing problems with split deliveries," Operational Research, Springer, vol. 21(1), pages 399-423, March.
    4. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    5. Cheng, Chun & Adulyasak, Yossiri & Rousseau, Louis-Martin, 2020. "Drone routing with energy function: Formulation and exact algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 364-387.
    6. Olcay Polat & Duygu Topaloğlu, 2022. "Collection of different types of milk with multi-tank tankers under uncertainty: a real case study," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 1-33, April.
    7. Ehmke, Jan Fabian & Campbell, Ann M. & Thomas, Barrett W., 2018. "Optimizing for total costs in vehicle routing in urban areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 242-265.
    8. Véronique François & Yasemin Arda & Yves Crama, 2019. "Adaptive Large Neighborhood Search for Multitrip Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 53(6), pages 1706-1730, November.
    9. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    10. Yuxin Liu & Zihang Qin & Jin Liu, 2023. "An Improved Genetic Algorithm for the Granularity-Based Split Vehicle Routing Problem with Simultaneous Delivery and Pickup," Mathematics, MDPI, vol. 11(15), pages 1-15, July.
    11. Li, Xiangyong & Wei, Kai & Aneja, Y.P. & Tian, Peng, 2017. "Design-balanced capacitated multicommodity network design with heterogeneous assets," Omega, Elsevier, vol. 67(C), pages 145-159.
    12. Ahern, Zeke & Paz, Alexander & Corry, Paul, 2022. "Approximate multi-objective optimization for integrated bus route design and service frequency setting," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 1-25.
    13. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    14. Zhang, Zhenzhen & Wei, Lijun & Lim, Andrew, 2015. "An evolutionary local search for the capacitated vehicle routing problem minimizing fuel consumption under three-dimensional loading constraints," Transportation Research Part B: Methodological, Elsevier, vol. 82(C), pages 20-35.
    15. Anselmo Ramalho Pitombeira-Neto & Bruno de Athayde Prata, 2020. "A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(1), pages 178-192, April.
    16. Hamed Farrokhi-Asl & Ahmad Makui & Armin Jabbarzadeh & Farnaz Barzinpour, 2020. "Solving a multi-objective sustainable waste collection problem considering a new collection network," Operational Research, Springer, vol. 20(4), pages 1977-2015, December.
    17. Frómeta Moya, Jorge Israel & Pérez Campos, Javier de Jesús, 2021. "Modelo heurístico híbrido para el ruteo vehicular y manejo de inventario en una entidad comercializadora de combustibles. || Hybrid heuristic model for inventory routing management in a fuel comercial," Revista de Métodos Cuantitativos para la Economía y la Empresa = Journal of Quantitative Methods for Economics and Business Administration, Universidad Pablo de Olavide, Department of Quantitative Methods for Economics and Business Administration, vol. 31(1), pages 363-383, June.
    18. Chen, Lijian & Chiang, Wen-Chyuan & Russell, Robert & Chen, Jun & Sun, Dengfeng, 2018. "The probabilistic vehicle routing problem with service guarantees," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 149-164.
    19. Florio, Alexandre M. & Gendreau, Michel & Hartl, Richard F. & Minner, Stefan & Vidal, Thibaut, 2023. "Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1081-1093.
    20. Salhi, Said & Wassan, Niaz & Hajarat, Mutaz, 2013. "The Fleet Size and Mix Vehicle Routing Problem with Backhauls: Formulation and Set Partitioning-based Heuristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 56(C), pages 22-35.

    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:spr:orspec:v:42:y:2020:i:1:d:10.1007_s00291-019-00570-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.