Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2016 | OriginalPaper | Buchkapitel

A Hybrid Constructive Mat-heuristic Algorithm for the Heterogeneous Vehicle Routing Problem with Simultaneous Pick-up and Delivery

verfasst von : Baris Kececi, Fulya Altiparmak, Imdat Kara

Erschienen in: Evolutionary Computation in Combinatorial Optimization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper, a variant of Vehicle Routing Problem, called Heterogeneous Vehicle Routing Problem with Simultaneous Pick-up and Delivery (HVRPSPD), is considered. The HVRPSPD can be defined as determining the routes and vehicle types on each route in such a way that the pickup and delivery demands of each customer must be performed with same vehicle, while minimizing the total cost. We propose a mathematical model for the problem and some valid inequalities for the model. Since the HVRPSPD is an NP-hard problem, the proposed mathematical model can be used to find the optimal solution for the small-size problems. Therefore we propose a hybrid mat-heuristic approach based on the formulation and Local Search to solve medium and large-size HVRPSPDs. A series of experiments is performed to evaluate the performance of proposed algorithm. Computational results show that hybrid mat-heuristic is computationally efficient to find good quality of initial solutions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Nächstes Kapitel A Property Preserving Method for Extending a Single-Objective Problem Instance to Multiple Objectives with Specific Correlations
Literatur
1.
2.
Toth, P., Vigo, D.: The vehicle routing problem. Society for Industrial and Applied Mathematics (2001)
3.
4.
Golden, B., Assad, A., Levy, L., Gheysens, F.: The fleet size and mix vehicle routing problem. Comput. Oper. Res. 11(1), 49–66 (1984)CrossRefMATH
5.
Salhi, S., Rand, G.K.: Incorporating vehicle routing into the vehicle fleet composition problem. Eur. J. Oper. Res. 66(3), 313–330 (1993)CrossRefMATH
6.
Gheysens, F., Golden, B., Assad, A.: A new heuristic for determining fleet size and composition. In: Gallo, G., Sandi, C. (eds.) Netflow at Pisa. Mathematical Programming Studies, vol. 26, pp. 233–236. Springer, Heidelberg (1986)CrossRef
7.
Taillard, É.D.: A heuristic column generation method for the heterogeneous fleet vrp. Revue française d’automatique, d’informatique et de Recherche Opérationnelle Recherche Opérationnelle 33(1), 1–14 (1999)
8.
Tarantilis, C.D., Kiranoudis, C.T., Vassiliadis, V.S.: A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Eur. J. Oper. Res. 152(1), 148–158 (2004)MathSciNetCrossRefMATH
9.
Baldacci, R., Toth, P., Vigo, D.: Exact algorithms for routing problems under vehicle capacity constraints. Ann. Oper. Res. 175(1), 213–245 (2010)MathSciNetCrossRefMATH
10.
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)MathSciNetCrossRefMATH
11.
Berbeglia, G., Cordeau, J.F., Gribkovskaia, I., Laporte, G.: Static pickup and delivery problems: a classification scheme and survey. Top 15(1), 1–31 (2007)MathSciNetCrossRefMATH
12.
Parragh, S.N., Doerner, K., Hartl, R.F.: A survey on pickup and delivery models part i: transportation between customers and depot. J. Betriebswirtschaft 58, 21–51 (2008)CrossRef
13.
Rieck, J., Zimmermann, J.: A hybrid algorithm for vehicle routing of less-than-truckload carriers. In: Sörensen, K., Sevaux, M., Habenicht, W., Geiger, M.J. (eds.) Metaheuristics in the Service Industry. Lecture Notes in Economics and Mathematical Systems, vol. 624, pp. 155–171. Springer, Heidelberg (2009)CrossRef
14.
Çetin, S., Gencer, C.: Heterojen araç filolu zaman pencereli eş zamanlı dağıtım-toplamalı araç rotalama problemleri: Matematiksel model. Int. J. Research Dev. 3(1), 19–27 (2011)
15.
Dethloff, J.: Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum 23(1), 79–96 (2001)MathSciNetCrossRefMATH
16.
Ríos-Mercado, R.Z., López-Pérez, J.F., Castrillón-Escobar, A.: A GRASP for a multi-depot multi-commodity pickup and delivery problem with time windows and heterogeneous fleet in the bottled beverage industry. In: Pacino, D., Voß, S., Jensen, R.M. (eds.) ICCL 2013. LNCS, vol. 8197, pp. 143–157. Springer, Heidelberg (2013)CrossRef
17.
Hoos, H.H., Stützle, T.: Stochastic local search: Foundations & applications. Elsevier (2004)
18.
Dantzig, G., Fulkerson, R., Johnson, S.: Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Am. 2(4), 393–410 (1954)MathSciNet
19.
Yaman, H.: Formulations and valid inequalities for the heterogeneous vehicle routing problem. Math. Program. 106(2), 365–390 (2006)MathSciNetCrossRefMATH
20.
Boschetti, M.A., Maniezzo, V., Roffilli, M., Bolufé Röhler, A.: Matheuristics: optimization, simulation and control. In: Blesa, M.J., Blum, C., Di Gaspero, L., Roli, A., Sampels, M., Schaerf, A. (eds.) HM 2009. LNCS, vol. 5818, pp. 171–177. Springer, Heidelberg (2009)CrossRef
21.
Croce, D.F., Salassa, F.: A variable neighborhood search based matheuristic for nurse rostering problems. Ann. Oper. Res. 218(1), 185–199 (2014)MathSciNetCrossRefMATH
22.
Della Croce, F., Grosso, A., Salassa, F.: A matheuristic approach for the total completion time permutation flow shop problem. Operations Research for Complex Decision Making, pp. 20 (2010)
23.
Puchinger, J., Raidl, G.R.: Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification. In: Mira, J., Álvarez, J.R. (eds.) IWINAC 2005. LNCS, vol. 3562, pp. 41–53. Springer, Heidelberg (2005)CrossRef
24.
Raidl, G.R., Puchinger, J.: Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. In: Blum, C., Aguilera, M.J.B., Roli, A., Sampels, M. (eds.) An Emerging Approach to Optimization. Studies in Computational Intelligence, vol. 114, pp. 31–62. Springer, Heidelberg (2008)CrossRef
25.
Maniezzo, V., Stützle, T., Vo, S.: Matheuristics: Hybridizing Metaheuristics and Mathematical Programming. Springer, Heidelberg (2010)CrossRef
26.
Dondo, R., Cerdá, J.: A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. Eur. J. Oper. Res. 176(3), 1478–1507 (2007)CrossRefMATH
27.
Liu, F.H., Shen, S.Y.: The fleet size and mix vehicle routing problem with time windows. J. Oper. Res. Soc. 50, 721–732 (1999)CrossRefMATH
28.
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987)MathSciNetCrossRefMATH
29.
Salhi, S., Nagy, G.: A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. J. oper. Res. Soc. 50, 1034–1042 (1999)CrossRefMATH
Metadaten
Titel
A Hybrid Constructive Mat-heuristic Algorithm for the Heterogeneous Vehicle Routing Problem with Simultaneous Pick-up and Delivery
verfasst von
Baris Kececi
Fulya Altiparmak
Imdat Kara
Copyright-Jahr
2016
Verlag
Springer International Publishing
Buch
Evolutionary Computation in Combinatorial Optimization

Print ISBN: 978-3-319-30697-1

Electronic ISBN: 978-3-319-30698-8

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-30698-8_1

Premium Partner

    Bildnachweise