×

Minimum makespan vehicle routing problem with compatibility constraints. (English) Zbl 1492.90098

Salvagnin, Domenico (ed.) et al., Integration of AI and OR techniques in constraint programming. 14th international conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10335, 244-253 (2017).
Summary: We study a multiple vehicle routing problem, in which a fleet of vehicles is available to serve different types of services demanded at locations. The goal is to minimize the makespan, i.e. the maximum length of any vehicle route. We formulate it as a mixed-integer linear program and propose a branch-cut-and-price algorithm. We also develop an efficient \(O(\log n)\)-approximation algorithm for this problem. We conduct numerical studies on Solomon’s instances with various demand distributions, network topologies, and fleet sizes. Results show that the approximation algorithm solves all the instances very efficiently and produces solutions with good practical bounds.
For the entire collection see [Zbl 1364.68017].

MSC:

90C11 Mixed integer programming
90B06 Transportation, logistics and supply chain management

Software:

CVRPSP; Gurobi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achuthan, N.R., Caccetta, L., Hill, S.P.: An improved branch-and-cut algorithm for the capacitated vehicle routing problem. Transp. Sci. 37(2), 153–169 (2003)
[2] Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River (1993) · Zbl 1201.90001
[3] Applegate, D., Cook, W., Dash, S., Rohe, A.: Solution of a min-max vehicle routing problem. INFORMS J. Comput. 14(2), 132–143 (2002) · Zbl 1238.90110
[4] Arkin, E.M., Hassin, R., Levin, A.: Approximations for minimum and min-max vehicle routing problems. J. Algorithms 59(1), 1–18 (2006) · Zbl 1112.68135
[5] Baldacci, R., Mingozzi, A., Roberti, R.: New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5), 1269–1283 (2011) · Zbl 1233.90059
[6] Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX/RANDOM 2004. LNCS, vol. 3122, pp. 72–83. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-27821-4_7
[7] Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959) · Zbl 0995.90560
[8] Even, G., Garg, N., Könemann, J., Ravi, R., Sinha, A.: Min-max tree covers of graphs. Oper. Res. Lett. 32(4), 309–315 (2004) · Zbl 1054.90079
[9] Feillet, D.: A tutorial on column generation and branch-and-price for vehicle routing problems. Q. J. Oper. Res. 8(4), 407–424 (2010) · Zbl 1208.90016
[10] 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(3), 216–229 (2004) · Zbl 1056.90014
[11] National Association for Home Care & Hospice. Basic Statistics About Home Care, pp. 1–14. National Association for Home Care & Hospice, Washington, DC (2010)
[12] Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: 17th Annual Symposium on Foundations of Computer Science, pp. 216–227. IEEE (1976)
[13] Fukasawa, R., Longo, H., Lysgaard, J., de Aragão, M.P., Reis, M., Uchoa, E., Werneck, R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106(3), 491–511 (2006) · Zbl 1094.90050
[14] Garg, N.: A 3-approximation for the minimum tree spanning \[ k \]
vertices. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, pp. 302–309. IEEE Computer Society, Washington, DC (1996)
[15] Golden, B.L., Raghavan, S., Wasil, E.A.: Problem, The Vehicle Routing: Latest Advances and New Challenges. Springer Science & Business Media, New York (2008) · Zbl 1142.90004
[16] Gurobi Optimization, Inc., Gurobi optimizer reference manual (2016). http://www.gurobi.com
[17] Jepsen, M., Petersen, B., Spoorendonk, S., Pisinger, D.: Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2), 497–511 (2008) · Zbl 1167.90413
[18] Kallehauge, B., Larsen, J., Madsen, O.B., Solomon, M.M.: Vehicle routing problem with time windows. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 67–98. Springer, New York (2005) · Zbl 1130.90316
[19] Letchford, A.N., Eglese, R.W., Lysgaard, J.: Multistars, partial multistars and the capacitated vehicle routing problem. Math. Program. 94(1), 21–40 (2002) · Zbl 1023.90073
[20] Lysgaard, J., Letchford, A.N., Eglese, R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program. 100(2), 423–445 (2004) · Zbl 1073.90068
[21] Pecin, D., Pessoa, A., Poggi, M., Uchoa, E.: Improved branch-cut-and-price for capacitated vehicle routing. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 393–403. Springer, Cham (2014). doi: 10.1007/978-3-319-07557-0_33 · Zbl 1418.90239
[22] Ralphs, T.K., Kopman, L., Pulleyblank, W.R., Trotter, L.E.: On the capacitated vehicle routing problem. Math. Program. 94(2–3), 343–359 (2003) · Zbl 1030.90131
[23] Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987) · Zbl 0625.90047
[24] Toth, P., Vigo, D., Routing, V.: Problems, Methods, and Applications. SIAM, Philadelphia (2014)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.