Route relaxations on GPU for vehicle routing problems. (English) Zbl 1394.90542

Summary: 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.


90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
90C39 Dynamic programming
90C60 Abstract computational complexity for mathematical programming problems


Full Text: DOI


[1] Augerat, P.; Belenguer, J. M.; Benavent, E.; Corberán, A.; Naddef, D.; Rinaldi, G., Computational results with a branch and cut code for the capacitated vehicle routing problem, Technical report 949-M, (1995), ARTEMIS-IMAG, Université Joseph Fourier Grenoble, France
[2] Baldacci, R.; Mingozzi, A.; Roberti, R., New route relaxation and pricing strategies for the vehicle routing problem, Operations Research, 59, 1269-1283, (2011) · Zbl 1233.90059
[3] Balinski, M.; Quandt, R., On an integer program for a delivery problem, Operations Research, 12, 2, 300-304, (1964)
[4] Boschetti, M.; Maniezzo, V., A set covering based matheuristic for a real-world city logistics problem, International Transactions in Operational Research, 22, 1, 169-195, (2015) · Zbl 1309.90010
[5] Boschetti, M.; Maniezzo, V.; Roffilli, M.; Bolufe Rohler, A., Matheuristics: optimization, simulation and control, (Blesa, M.; Blum, C.; Di Gaspero, L.; Roli, A.; Samples, M.; A., S., Hybrid metaheuristics. LNCS, Vol. 5818, (2009), Springer), 171-177
[6] Boschetti, M.; Maniezzo, V.; Strappaveccia, F., Using GPU computing for solving the two-dimensional guillotine cutting problem, INFORMS Journal on Computing, 28, 3, 540-552, (2016) · Zbl 1348.90501
[7] Boyer, V.; El Baz, D.; Moussa, E., Solving knapsack problems on GPU, Computers & Operations Research, 39, 1, 42-47, (2012) · Zbl 1251.90014
[8] Brodtkorb, A.; Hagen, T.; Schulz, C.; Hasle, G., GPU computing in discrete optimization. part I: introduction to the GPU, EURO Journal on Transportation and Logistics, 2, 1-2, 129-157, (2013)
[9] Buluç, A.; Gilbert, J.; Budak, C., Solving path problems on the GPU, Parallel Computing, 36, 5, 241-253, (2010) · Zbl 1204.68043
[10] Christofides, N.; Eilon, S., An algorithm for the vehicle-dispatching problem, Operational Research Quarterly, 20, 3, 309-318, (1969)
[11] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem based on spanning tree and shortest path relaxation, Mathematical Programming, 10, 255-280, (1981) · Zbl 0461.90067
[12] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Mathematical Programming, 20, 255-282, (1981) · Zbl 0461.90067
[13] Christofides, N.; Mingozzi, A.; Toth, P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11(2), 145-164, (1981) · Zbl 0458.90071
[14] CVRPLIB (2015). Capacitated vehicle routing problem library. http://vrp.atd-lab.inf.puc-rio.br/index.php/en/. Accessed: 18.09.15.
[15] Dantzig, G.; Ramser, J., The truck dispatching problem, Management Science, 6, 1, 80-91, (1959) · Zbl 0995.90560
[16] Desrochers, M.; Desrosiers, J.; Solomon, M., A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, 40, 2, 342-354, (1992) · Zbl 0749.90025
[17] Dror, M., Noteon the complexity of the shortest path models for column generation in VRPTW, Operations Research, 42, 977-978, (1994) · Zbl 0815.90064
[18] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems, Networks, 44, 216-229, (2004) · Zbl 1056.90014
[19] Fisher, M., Optimal solution of vehicle routing problem using minimum k-trees, Operations Research, 42, 626-642, (1994) · Zbl 0815.90066
[20] (Golden, B.; Raghavan, S.; Wasil, E., The vehicle routing problem: Latest advances and new challenges, Operations Research/Computer Science Interfaces Series, Vol. 43, (2008), Springer) · Zbl 1142.90004
[21] Harish, P.; Vineet, V.; Narayanan, P., Large graph algorithms for massively multithreaded architectures, Technical Report, (2009), Centre for Visual Information Technology, Institute of Information Technology Hyderabad, India
[22] Harris, M. (2009). Optimizing parallel reduction in CUDA. Nvidia developer zone. http://developer.download.nvidia.com/assets/cuda/files/reduction.pdf.
[23] Irnich, S.; Villeneuve, D., The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3, INFORMS Journal on Computing, 18, 3, 391-406, (2006) · Zbl 1241.90161
[24] Katz, G.; Kider Jr, J., All-pairs shortest-paths for large graphs on the GPU, Proceedings of the 23rd ACM SIGGRAPH/Eurographics symposium on graphics hardware, GH’08, 47-55, (2008), Eurographics Association Aire-la-Ville, Switzerland, Switzerland, http://dl.acm.org/citation.cfm?id=1413957.1413966
[25] Kumar, S.; Misra, A.; Tomar, R., A modified parallel approach to single source shortest path problem for massively dense graphs using CUDA, Second international conference on computer and communication technology (ICCCT), 635-639, (2011), IEEE
[26] Li, F.; Golden, B.; Wasil, E., Very large-scale vehicle routing: new test problems, algorithms, and results, Computers & Operations Research, 32, 5, 1165-1179, (2005) · Zbl 1075.90013
[27] Lund, B. D.; Smith, J. W., A multi-stage CUDA kernel for floyd-warshall, CoRR, (2010)
[28] Lysgaard, J.; Letchford, A.; Eglese, R., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Mathematical Programming, 100, 2, 423-445, (2004) · Zbl 1073.90068
[29] Martinelli, R.; Pecin, D.; Poggi, M., Efficient elementary and restricted non-elementary route pricing, European Journal of Operational Research, 239, 1, 102-111, (2014) · Zbl 1339.90061
[30] Nvidia (2007). Nvidia developer zone. https://developer.nvidia.com/. Accessed: 03.12.13.
[31] Ortega-Arranz, H.; Torres, Y.; Llanos, D.; Gonzalez-Escribano, A., A new GPU-based approach to the shortest path problem, International conference on high performance computing and simulation (HPCS), 505-511, (2013), IEEE
[32] Ou, W.; Sun, B.-G., A dynamic programming algorithm for vehicle routing problems, Proceedings of the 2010 international conference on computational and information sciences (ICCIS ’10), 733-736, (2010), IEEE Computer Society Washington, DC, USA
[33] Righini, G.; Salani, M., Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optimization, 3, 3, 255-273, (2006) · Zbl 1149.90167
[34] Righini, G.; Salani, M., New dynamic programming algorithms for the resource constrained elementary shortest path, Networks, 51, 3, 155-170, (2008) · Zbl 1144.90514
[35] Righini, G.; Salani, M., Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming, Computers & Operations Research, 36, 4, 1191-1203, (2009) · Zbl 1162.90548
[36] Schulz, C., Efficient local search on the GPU—investigations on the vehicle routing problem, Journal of Parallel and Distributed Computing, 73, 1, 14-31, (2013)
[37] Schulz, C.; Hasle, G.; Brodtkorb, A. R.; Hagen, T., GPU computing in discrete optimization. part II: survey focused on routing problems, EURO Journal on Transportation and Logistics, 2, 1-2, 159-186, (2013)
[38] Stone, J. E.; Hardy, D. J.; Ufimtsev, I. S.; Schulten, K., GPU-accelerated molecular modeling coming of age, Journal of Molecular Graphics and Modelling, 29, 2, 116-125, (2010)
[39] (Toth, P.; Vigo, D., (2001), Society for Industrial and Applied Mathematics Philadelphia, PA, USA)
[40] VeroLog (2014). http://www.verolog.eu/.
[41] VRPLIB (2015). Vehicle Routing Problem LIBrary. http://or.dei.unibo.it/library/vrplib-vehicle-routing-problem-library. Accessed: 18.09.15.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.