IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v30y2018i4p694-709.html
   My bibliography  Save this article

A Joint Vehicle Routing and Speed Optimization Problem

Author

Listed:
  • Ricardo Fukasawa

    (Department of Combinatorics and Optimization, University of Waterloo, Ontario N2L 3G1, Canada)

  • Qie He

    (Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455)

  • Fernando Santos

    (Department of Engineering, Campus Itabira, Federal University of Itajubá, Itajubá, Brazil)

  • Yongjia Song

    (Department of Statistical Sciences and Operations Research, Virginia Commonwealth University, Richmond, Virginia 23284)

Abstract

Classic vehicle routing models usually treat fuel cost as input data, but fuel consumption heavily depends on the travel speed, which leads to the study of optimizing speeds over a route to improve fuel efficiency. In this paper, we propose a joint vehicle routing and speed optimization problem to minimize the total operating cost including fuel cost. The only assumption made on the dependence between fuel cost and travel speed is that it is a strictly convex differentiable function. This problem is very challenging, with medium-sized instances already difficult for a general mixed-integer convex optimization solver. We propose a novel set-partitioning formulation and a branch-cut-and-price algorithm to solve this problem. We introduce new dominance rules for the labeling algorithm so that the pricing problem can be solved efficiently. Our algorithm clearly outperforms the off-the-shelf optimization solver, and is able to solve some benchmark instances to optimality for the first time. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0810 .

Suggested Citation

  • Ricardo Fukasawa & Qie He & Fernando Santos & Yongjia Song, 2018. "A Joint Vehicle Routing and Speed Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 694-709, November.
    • Handle: RePEc:inm:orijoc:v:30:y:2018:i:4:p:694-709
    DOI: 10.1287/ijoc.2018.0810
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0810
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0810?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
    ---><---

    References listed on IDEAS

    as
    1. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2011. "New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem," Operations Research, INFORMS, vol. 59(5), pages 1269-1283, October.
    2. Tolga Bektaş & Emrah Demir & Gilbert Laporte, 2016. "Green Vehicle Routing," International Series in Operations Research & Management Science, in: Harilaos N. Psaraftis (ed.), Green Transportation Logistics, edition 127, chapter 0, pages 243-265, Springer.
    3. K Fagerholt & G Laporte & I Norstad, 2010. "Reducing fuel emissions by optimizing speed on shipping routes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(3), pages 523-529, March.
    4. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    5. Michael Maloni & Jomon Aliyas Paul & David M Gligor, 2013. "Slow steaming impacts on ocean carriers and shippers," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 15(2), pages 151-171, June.
    6. J Fernando Alvarez & Tore Longva & Erna S Engebrethsen, 2010. "A methodology to assess vessel berthing and speed optimization policies," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 12(4), pages 327-346, December.
    7. Wang, Shuaian, 2016. "Fundamental properties and pseudo-polynomial-time algorithm for network containership sailing speed optimization," European Journal of Operational Research, Elsevier, vol. 250(1), pages 46-55.
    8. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    9. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    10. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    11. Du, Yuquan & Chen, Qiushuang & Quan, Xiongwen & Long, Lei & Fung, Richard Y.K., 2011. "Berth allocation considering fuel consumption and vessel emissions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 1021-1037.
    12. Jun Xia & Kevin X. Li & Hong Ma & Zhou Xu, 2015. "Joint Planning of Fleet Deployment, Speed Optimization, and Cargo Allocation for Liner Shipping," Transportation Science, INFORMS, vol. 49(4), pages 922-938, November.
    13. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "A review of recent research on green road freight transportation," European Journal of Operational Research, Elsevier, vol. 237(3), pages 775-793.
    14. Kramer, Raphael & Maculan, Nelson & Subramanian, Anand & Vidal, Thibaut, 2015. "A speed and departure time optimization algorithm for the pollution-routing problem," European Journal of Operational Research, Elsevier, vol. 247(3), pages 782-787.
    15. 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.
    16. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    17. Moshe Dror, 1994. "Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW," Operations Research, INFORMS, vol. 42(5), pages 977-978, October.
    18. Sanjeeb Dash & Oktay Günlük & Andrea Lodi & Andrea Tramontani, 2012. "A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 132-147, February.
    19. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    20. Notteboom, Theo E. & Vernimmen, Bert, 2009. "The effect of high fuel costs on liner service configuration in container shipping," Journal of Transport Geography, Elsevier, vol. 17(5), pages 325-337.
    21. Wang, Shuaian & Meng, Qiang, 2012. "Sailing speed optimization for container ships in a liner shipping network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 701-714.
    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. 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.
    2. Lera-Romero, Gonzalo & Miranda Bront, Juan José & Soulignac, Francisco J., 2024. "A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 312(3), pages 978-995.
    3. Zeyang Wu & Kameng Nip & Qie He, 2021. "A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1197-1212, July.

    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. Fukasawa, Ricardo & He, Qie & Song, Yongjia, 2016. "A disjunctive convex programming approach to the pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 61-79.
    2. He, Qie & Zhang, Xiaochen & Nip, Kameng, 2017. "Speed optimization over a path with heterogeneous arc costs," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 198-214.
    3. Guy Desaulniers & Diego Pecin & Claudio Contardo, 2019. "Selective pricing in branch-price-and-cut algorithms for vehicle routing," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(2), pages 147-168, June.
    4. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    5. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    6. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    7. Yiming Liu & Yang Yu & Yu Zhang & Roberto Baldacci & Jiafu Tang & Xinggang Luo & Wei Sun, 2023. "Branch-Cut-and-Price for the Time-Dependent Green Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 14-30, January.
    8. Shyam S. G. Perumal & Jesper Larsen & Richard M. Lusby & Morten Riis & Tue R. L. Christensen, 2022. "A column generation approach for the driver scheduling problem with staff cars," Public Transport, Springer, vol. 14(3), pages 705-738, October.
    9. Diego Pecin & Claudio Contardo & Guy Desaulniers & Eduardo Uchoa, 2017. "New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 489-502, August.
    10. Emilio Zamorano & Annika Becker & Raik Stolletz, 2018. "Task assignment with start time-dependent processing times for personnel at check-in counters," Journal of Scheduling, Springer, vol. 21(1), pages 93-109, February.
    11. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    12. Yan, Ran & Wang, Shuaian & Du, Yuquan, 2020. "Development of a two-stage ship fuel consumption prediction and reduction model for a dry bulk ship," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    13. Qie He & Stefan Irnich & Yongjia Song, 2019. "Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Transportation Science, INFORMS, vol. 53(5), pages 1409-1426, September.
    14. Said Dabia & Emrah Demir & Tom Van Woensel, 2017. "An Exact Approach for a Variant of the Pollution-Routing Problem," Transportation Science, INFORMS, vol. 51(2), pages 607-628, May.
    15. Iman Dayarian & Guy Desaulniers, 2019. "A Branch-Price-and-Cut Algorithm for a Production-Routing Problem with Short-Life-Span Products," Transportation Science, INFORMS, vol. 53(3), pages 829-849, May.
    16. Veaceslav Ghilas & Jean-François Cordeau & Emrah Demir & Tom Van Woensel, 2018. "Branch-and-Price for the Pickup and Delivery Problem with Time Windows and Scheduled Lines," Transportation Science, INFORMS, vol. 52(5), pages 1191-1210, October.
    17. Emna Marrekchi & Walid Besbes & Diala Dhouib & Emrah Demir, 2021. "A review of recent advances in the operations research literature on the green routing problem and its variants," Annals of Operations Research, Springer, vol. 304(1), pages 529-574, September.
    18. Koza, David Franz, 2019. "Liner shipping service scheduling and cargo allocation," European Journal of Operational Research, Elsevier, vol. 275(3), pages 897-915.
    19. Stefan Irnich & Guy Desaulniers & Jacques Desrosiers & Ahmed Hadjar, 2010. "Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 297-313, May.
    20. Gschwind, Timo, 2015. "A comparison of column-generation approaches to the Synchronized Pickup and Delivery Problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 60-71.

    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:inm:orijoc:v:30:y:2018:i:4:p:694-709. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.