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

Route relaxations on GPU for vehicle routing problems

Author

Listed:
  • Boschetti, Marco Antonio
  • Maniezzo, Vittorio
  • Strappaveccia, Francesco

Abstract

State-Space Relaxation (SSR) is an approach often used to compute by dynamic programming (DP) effective bounds for many combinatorial optimization problems. Currently, the most effective exact approaches for solving many Vehicle Routing Problems (VRPs) are DP algorithms making use of SSR for computing their bounding components. In particular, most of these make use of the q-route and ng-route relaxations. The bounding procedures based on these relaxations provide good quality bounds but they are often time consuming to compute, even for moderate size instances. In this paper we investigate the use of GPU computing for solving q-route and ng-route relaxations. The results prove that the proposed GPU implementations are able to achieve remarkable computing time reductions, up to 40 times with respect to the sequential versions.

Suggested Citation

  • Boschetti, Marco Antonio & Maniezzo, Vittorio & Strappaveccia, Francesco, 2017. "Route relaxations on GPU for vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 456-466.
    • Handle: RePEc:eee:ejores:v:258:y:2017:i:2:p:456-466
    DOI: 10.1016/j.ejor.2016.09.050
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716308025
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.09.050?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. Marshall L. Fisher, 1994. "Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees," Operations Research, INFORMS, vol. 42(4), pages 626-642, August.
    2. M. L. Balinski & R. E. Quandt, 1964. "On an Integer Program for a Delivery Problem," Operations Research, INFORMS, vol. 12(2), pages 300-304, April.
    3. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    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. Martinelli, Rafael & Pecin, Diego & Poggi, Marcus, 2014. "Efficient elementary and restricted non-elementary route pricing," European Journal of Operational Research, Elsevier, vol. 239(1), pages 102-111.
    6. Marco A. Boschetti & Vittorio Maniezzo & Francesco Strappaveccia, 2016. "Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 540-552, August.
    7. 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.
    8. Stefan Irnich & Daniel Villeneuve, 2006. "The Shortest-Path Problem with Resource Constraints and k -Cycle Elimination for k (ge) 3," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 391-406, August.
    9. Zhang, Jianghua & Zhao, Yingxue & Xue, Weili & Li, Jin, 2015. "Vehicle routing problem with fuel consumption and carbon emission," International Journal of Production Economics, Elsevier, vol. 170(PA), pages 234-242.
    10. 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.
    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. Bach, Lukas & Hasle, Geir & Schulz, Christian, 2019. "Adaptive Large Neighborhood Search on the Graphics Processing Unit," European Journal of Operational Research, Elsevier, vol. 275(1), pages 53-66.
    2. 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.

    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. 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.
    2. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2015. "A column generation approach for a multi-attribute vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 888-906.
    3. Dollevoet, T.A.B. & Pecin, D. & Spliet, R., 2020. "The path programming problem and a partial path relaxation," Econometric Institute Research Papers EI-2020-04, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. 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.
    5. Bulhões, Teobaldo & Hà, Minh Hoàng & Martinelli, Rafael & Vidal, Thibaut, 2018. "The vehicle routing problem with service level constraints," European Journal of Operational Research, Elsevier, vol. 265(2), pages 544-558.
    6. 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.
    7. Bhusiri, Narath & Qureshi, Ali Gul & Taniguchi, Eiichi, 2014. "The trade-off between fixed vehicle costs and time-dependent arrival penalties in a routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 1-22.
    8. Yao, Yu & Van Woensel, Tom & Veelenturf, Lucas P. & Mo, Pengli, 2021. "The consistent vehicle routing problem considering path consistency in a road network," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 21-44.
    9. Reihaneh, Mohammad & Ghoniem, Ahmed, 2019. "A branch-and-price algorithm for a vehicle routing with demand allocation problem," European Journal of Operational Research, Elsevier, vol. 272(2), pages 523-538.
    10. Line Blander Reinhardt & Mads Kehlet Jepsen & David Pisinger, 2016. "The Edge Set Cost of the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 50(2), pages 694-707, May.
    11. Bode, Claudia & Irnich, Stefan, 2014. "The shortest-path problem with resource constraints with (k,2)-loop elimination and its application to the capacitated arc-routing problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 415-426.
    12. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    13. Baldacci, Roberto & Mingozzi, Aristide & Roberti, Roberto, 2012. "Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints," European Journal of Operational Research, Elsevier, vol. 218(1), pages 1-6.
    14. Timo Gschwind & Stefan Irnich, 2012. "Effective Handling of Dynamic Time Windows and Synchronization with Precedences for Exact Vehicle Routing," Working Papers 1211, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    15. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    16. Range, Troels Martin, 2013. "Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints," Discussion Papers on Economics 17/2013, University of Southern Denmark, Department of Economics.
    17. Letchford, Adam N. & Salazar-González, Juan-José, 2019. "The Capacitated Vehicle Routing Problem: Stronger bounds in pseudo-polynomial time," European Journal of Operational Research, Elsevier, vol. 272(1), pages 24-31.
    18. Leonardo Lozano & Daniel Duque & Andrés L. Medaglia, 2016. "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints," Transportation Science, INFORMS, vol. 50(1), pages 348-357, February.
    19. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    20. Nikolaus Furian & Michael O’Sullivan & Cameron Walker & Eranda Çela, 2021. "A machine learning-based branch and price algorithm for a sampled vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 693-732, September.

    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:258:y:2017:i:2:p:456-466. 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.