Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Modular Lipschitzian and Contractive Maps Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Modeling and Solving Vehicle Routing Problems with Many Available Vehicle Types

Authors : Sandra Eriksson Barman, Peter Lindroth, Ann-Brith Strömberg

Published in: Optimization, Control, and Applications in the Information Age

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Vehicle routing problems (VRPs) involving the selection of vehicles from a large set of vehicle types are hitherto not well studied in the literature. Such problems arise at Volvo Group Trucks Technology, that faces an immense set of possible vehicle configurations, of which an optimal set needs to be chosen for each specific combination of transport missions. Another property of real-world VRPs that is often neglected in the literature is that the fuel resources required to drive a vehicle along a route is highly dependent on the actual load of the vehicle.
We define the fleet size and mix VRP with many available vehicle types, called many-FSMVRP, and suggest an extended set-partitioning model of this computationally demanding combinatorial optimization problem. To solve the extended model, we have developed a method based on Benders decomposition, the subproblems of which are solved using column generation, and the column generation subproblems being solved using dynamic programming; the method is implemented with a so-called projection-of-routes procedure. The resulting method is compared with a column generation approach for the standard set-partitioning model. Our method for the extended model performs on par with column generation applied to the standard model for instances such that the two models are equivalent. In addition, the utility of the extended model for instances with very many available vehicle types is demonstrated. Our method is also shown to efficiently handle cases in which the costs are dependent on the load of the vehicle.
Computational tests on a set of extended standard test instances show that our method, based on Benders’ algorithm, is able to determine combinations of vehicles and routes that are optimal to a relaxation (w.r.t. the route decision variables) of the extended model. Our exact implementation of Benders’ algorithm appears, however, too slow when the number of customers grows. To improve its performance, we suggest that relaxed versions of the column generation subproblems are solved and that the set-partitioning model is replaced by a set-covering model.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter On the Sensitivity of Least Squares Data Fitting by Nonnegative Second Divided Differences
next chapter A Genetic Algorithm for Scheduling Alternative Tasks Subject to Technical Failure
Appendix
Available only for authorised users
Footnotes
1
Finite convergence is guaranteed if an optimal solution \((\pmb{\pi }^{L},\pmb{\gamma }^{L})\) to \(\mbox{ [BendersSPDual($\tilde{\mathbf{y}}^{L}$)]}\) is used to generate a new constraint to [BendersRMP] in each iteration, since if \(\tilde{\mathbf{y}}^{\ell_{1}} =\tilde{ \mathbf{y}}^{\ell_{2}}\), for two Benders iterations ℓ 1 < ℓ 2, then the optimality criterion (12) will be fulfilled at iteration ℓ 2.
 
Literature
1.
Baldacci, R., Mingozzi, A.: A unified exact method for solving different classes of vehicle routing problems. Math. Programm. 120(2), 347–380 (2009)
2.
Baldacci, R., Battarra, M., Vigo, D.: Routing a heterogeneous fleet of vehicles. In: Golden, B.L., Raghavan, S., Wasil, E.A. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, vol. 43, pp. 3–27. Springer, New York (2008)
3.
Balinski, L.M., Quandt, R.E.: On an integer program for a delivery problem. Oper. Res. 12(2), 300–304 (1964)
4.
Bettinelli, A., Ceselli, A., Righini, G.: A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transp. Res. C 19(5), 723–740 (2011)
5.
Boschetti, M., Maniezzo, V.: Benders decomposition, Lagrangean relaxation and metaheuristic design. J. Heuristics 15(3), 283–312 (2009)
6.
Choi, E., Tcha, D-W.: A column generation approach to the heterogeneous fleet vehicle routing problem. Oper. Res. 34(7), 2080–2095 (2007)
7.
Christofides, N., Eilon, S.: An algorithm for the vehicle-dispatching problem. OR 20(3), 309–318 (1969)
8.
Cordeau, J., Stojković, G., Soumis, F., Desrosiers, J.: Benders decomposition for simultaneous aircraft routing and crew scheduling. Transp. Sci. 35(4), 375–388 (2001)
9.
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manag. Sci. 6(1), 80–91 (1959)
10.
Díaz, B.D.: The VRP Web: VRP Instances, Nov 2006
11.
Drexl, M.: Rich vehicle routing in theory and practice. Logist. Res. 5(1–2), 47–63 (2012)
12.
Eriksson Barman, S.: Modeling and solving vehicle routing problems with many available vehicle types. Master’s thesis, University of Gothenburg, Sweden (2014)
13.
Feillet, D.: A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR 8(4), 407–424 (2010)
14.
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)
15.
Glover, F., Laguna, M.: Tabu search. In: Pardalos, P.M., Du, D., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 3261–3362. Springer, SIAM Publishing, New York (2013)
16.
Golden, B.L., Assad, A., Levy, L., Gheysens, F.: The fleet size and mix vehicle routing problem. Comput. Oper. Res. 11(1), 49–66 (1984)
17.
Hoff, A., Andersson, H., Christiansen, M., Hasle, G., Løkketangen, A.: Industrial aspects and literature survey: fleet composition and routing. Comput. Oper. Res. 37(12), 2041–2061 (2010)
18.
Irnich, S., Desaulniers, G.: Shortest path problems with resource constraints. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 33–65. Springer, New York (2005)
19.
Lasdon, L.S.: Optimization Theory for Large Systems. Macmillan, London (Reprinted by Dover Publications, Mineola, NY, 2002) (1970)
20.
Lübbecke, M.E., Desrosiers, J.: Selected topics in column generation. Oper. Res. 53(6), 1007–1023 (2005)
21.
Pessoa, A., Poggi de Aragão, M., Uchoa, E.: A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem. In: Demetrescu, C. (ed.) Experimental Algorithms. Lecture Notes in Computer Science, vol. 4525, pp. 150–160. Springer, Berlin (2007)
22.
Righini, G., Salani, M.: New dynamic programming algorithms for the resource constrained shortest path problem. Networks 51(3), 155–170 (2008)
23.
Taillard, E.D.: A heuristic column generation method for the heterogeneous fleet VRP. RAIRO: Oper. Res. 33(1), 1–14 (1999)
24.
Toth, P., Vigo, D.: An overview of vehicle routing problems. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, pp.1–26. SIAM Publishing, Philadelphia, PA (2002)
25.
Toth, P., Vigo, D.: Preface. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, pp. xvii–xviii. SIAM Publishing, Philadelphia, PA (2002)
26.
Vanderbeck, F.: On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper. Res. 48(1), 111–128 (2000)
27.
Vanderbeck, F.: Implementing mixed integer column generation. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 331–358. Springer, New York (2005)
28.
Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. Eur. J. Oper. Res. 231(1), 1–21 (2013)
29.
Xiao, Y., Zhao, Q., Kaku, I., Xu, Y.: Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Comput. Oper. Res. 39(7), 1419–1431 (2012)
Metadata
Title
Modeling and Solving Vehicle Routing Problems with Many Available Vehicle Types
Authors
Sandra Eriksson Barman
Peter Lindroth
Ann-Brith Strömberg
Copyright Year
2015
Book
Optimization, Control, and Applications in the Information Age

Print ISBN: 978-3-319-18566-8

Electronic ISBN: 978-3-319-18567-5

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-18567-5_6

Premium Partner

    Image Credits