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
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Mobile Networks and Applications
Erschienen in: Mobile Networks and Applications 1/2016

01.02.2016

Evolutionary Multiobjective Optimization for the Pickup and Delivery Problem with Time Windows and Demands

verfasst von: Dũng H. Phan, Junichi Suzuki

Erschienen in: Mobile Networks and Applications | Ausgabe 1/2016

Einloggen

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

search-config
loading …

Abstract

This paper studies an evolutionary algorithm to solve a new multiobjective optimization problem, the Pickup and Delivery Problem with Time Windows and Demands (PDP-TW-D), which is applicable to operational optimization in various mobile network systems. With respect to multiple optimization objectives, PDP-TW-D is to find a set of Pareto-optimal routes for a fleet of vehicles (e.g., mobile robots, drones and autonomous heavy-haulage trucks) in order to serve given transportation requests. The proposed algorithm uses a population of individuals, each of which represents a solution candidate, and evolves them through generations to seek the Pareto-optimal solutions. In addition to the evolution-based global search process, the proposed algorithm allows individuals to improve their optimality in each generation with a local search process, which is designed based on iterative neighborhood search. Experimental results demonstrate that the integration of global and local search processes improves the optimality of individuals and expedites convergence speed. The proposed algorithm outperforms two well-known existing EMOAs, NSGA-II and MOEA/D, in relatively large-scale problems that have up to 400 pickup and delivery locations.
Vorheriger Artikel Epistatic Signaling and Minority Games, the Adversarial Dynamics in Social Technological Systems
Nächster Artikel The Structural Role of Feed-Forward Loop Motif in Transcriptional Regulatory Networks

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
Weitere Produktempfehlungen anzeigen
Fußnoten
Literatur
1.
Ackerman E (2015) Fetch robotics introduces fetch and freight: your warehouse is now automated. IEEE Spectrum
2.
Auger A, Bader J, Brockhoff D, Zitzler E (2009) Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point. In: Proceedings of ACM workshop on foundations of genetic algorithms
3.
4.
Bent R, Hentenryck PV (2006) A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Comput Oper Res 33(4):875–893CrossRefMATH
5.
Brockhoff D, Wagner T, Trautmann H (2012) On the properties of the R2 indicator. In: Proceedings of ACM international genetic and evolutionary computation conference
6.
Brown C (2012) Autonomous vehicle technology in mining. Eng Min J 213(1):30–32
7.
Christiansen M (1999) Decomposition of a combined inventory routing and time constrained ship routing problem. Transp Sci 33(1):3–16CrossRefMATH
8.
Creput J-C, Koukam A, Kozlak J, Lukasik J (2004) An evolutionary approach to pickup and delivery problem with time windows. In: Proceedings of international conference on computational science
9.
10.
Deb K, Agrawal S, Pratap A, Meyarivan T (2001) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. In: Proceedings of international conference on parallel problem solving from nature
11.
Ding G, Li L, Ju Y (2009) Multi-strategy grouping genetic algorithm for the pickup and delivery problem with time windows. In: Proceedings of ACM international genetic and evolutionary computation conference
12.
D’Souza C, Omkar SN, Senthilnath J (2012) Pickup and delivery problem using metaheuristic techniques. Expert Syst Appl Int J 39(1):328–334CrossRef
13.
Durillo J, Nebro A, Alba E (2010) The jMetal framework for multi-objective optimization: design and architecture. In: Proceedings of IEEE congress on evolutionary computation
14.
Fisher ML, Rosenwein MB (1989) An interactive optimization system for bulk-cargo ship scheduling. Naval Res Logist Q 35:27–42CrossRef
15.
Hansen MP, Jaszkiewicz A (1998) Evaluating the quality of approximations of the non-dominated set. Technical Report IMM-REP-1998-7, Technical University of Denmark
16.
Knight W (2015) Inside amazon’s warehouse, human-robot symbiosis. MIT Technology Review
17.
Lau HC, Liang Z (2001) Pickup and delivery with time windows: algorithms and test case generation. In: Proceedings of IEEE international conference on tools with artificial intelligence
18.
Li H, Lim A (2001) A metaheuristic for the pickup and delivery problem with time windows. In: Proceedings of IEEE international conference on tools with artificial intelligence
19.
Liang C, Chee KJ, Zou Y, Zhu H, Causo A, Vidas S, Teng T, Chen IM, Low KH, Cheah CC (2015) Automated robot picking system for e-commerce fulfillment warehouse application. In: International federation for the promotion of mechanism and machine science
20.
Lien L (2011) Mining’s new future: how the industry will change in the next decade. Min Eng 63(2):41–46
21.
Madsen OBG, Ravn HF, Rygaard JM (1995) A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities and multiple objectives. Ann Oper Res 60(1):193–208CrossRefMATH
22.
Najera AG, Bullinaria JA (2009) Bi-objective optimization for the vehicle routing problem with time windows: using route similarity to enhance performance. In: Proceedings of international conference on evolutionary multi-criterion optimization
23.
Nanry WP, Barnes J (2000) Solving the pickup and delivery problem with time windows using reactive tabu search. Transp Res B Methodol 34(2):107–121CrossRef
24.
Ombuki B, Ross BJ, Hanshar F (2006) Multi-objective genetic algorithms for vehicle routing problem with time windows. Appl Intell 24(1):17–30CrossRef
25.
Pankratz G (2005) A grouping genetic algorithm for the pickup and delivery problem with time windows. OR Spectr 27(1):21–41MathSciNetCrossRefMATH
26.
Parragh S, Doerner K, Hartl R (2008) A survey on pickup and delivery problems: part I: transportation between customers and depot. Journal für Betriebswirtschaft 58(2):21–51CrossRef
27.
Parragh S, Doerner K, Hartl R (2008) A survey on pickup and delivery problems: Part II: Transportation between pickup and delivery locations. Journal für Betriebswirtschaft 58(2):81–117CrossRef
28.
Phan D, Suzuki J (2015) R2 indicator based multiobjective memetic optimization for the pickup and delivery problem with time windows and demands (PDP-TW-D). In: International conference on bio-inspired information and communications technologies
29.
Psaraftis HN (1980) A dynamic programming solution to the single-vehicle many-to-many dial-a-ride problem with time windows. Transp Sci 14(2):130–154CrossRef
30.
Psaraftis HN (1983) An exact algorithm for the single-vehicle many-to-many dial-a-ride problem with time windows. Transp Sci 17(3):351–357CrossRef
31.
Psaraftis HN, Orlin JB, Bienstock D, Thompson PM (1985) Analysis and solution algorithms of sealift routing and scheduling problems. Technical Report 1700-85, Massachusetts Institute of Technology, Sloan School of Management
32.
Rappoport HK, Levy LS, Golden BL, Toussaint K (1992) A planning heuristic for military airlift. Interfaces 22(3):73–87CrossRef
33.
Rappoport HK, Levy LS, Toussaint K, Golden BL (1994) A transportation problem formulation for the mac airlift planning problem. Ann Oper Res 50(1):505–523CrossRefMATH
34.
Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40(4):455–472CrossRef
35.
Solanki RS, Shouthworth F (1991) An execution planning algorithm for military airlift. Interfaces 21 (4):121–131CrossRef
36.
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265MathSciNetCrossRefMATH
37.
Solomon MM, Chalifour A, Desrosiers J, Boisvert J (1992) An application of vehicle routing methodology to large-scale larvicide control programs. Interfaces 22(3):88–99CrossRef
38.
Takoudjou RT, Deschamps JC, Dupas R (2012) A hybrid multi-start heuristic for the pickup and delivery problem with and without transshipment. In: Proceedings of international conference of modeling, optimization and simulation
39.
Tan KC, Chew YH, Lee LH (2006) A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Comput Optim Appl 34:115–151MathSciNetCrossRefMATH
40.
41.
Trautmann H, Wagner T, Brockhoff D (2013) R2-EMOA: focused multiobjective search using R2-indicator-based selection. In: Proceedings of learning and intelligent optimization conference
42.
Velasco N, Castagliola P, Dejax P, Guret C, Prins C (2009) A memetic algorithm for a pick-up and delivery problem by helicopter. In: Pereira F, Tavares J (eds) Bio-inspired algorithms for the vehicle routing problem. Springer, pp 173–190
43.
Wang H, Lee D-H, Cheu R (2009) PDPTW based taxi dispatch modeling for booking service. In: Proceedings of international conference on natural computation
44.
Wang HF, Chen YY (2012) A genetic algorithm for the simultaneous delivery and pickup problems with time window. Comput Ind Eng 62(1):84–95CrossRef
45.
Zhang Q, Li H (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731CrossRef
46.
Zitzler E, Knowles J, Thiele L (2008) Quality assessment of pareto set approximations. In: Branke J, Deb K, Miettinen K, Slowinski R (eds) Multiobjective optimization: interactive and evolutionary approaches. Springer, pp 373–404
47.
Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms: a comparative study. In: Proceedings of international conference on parallel problem solving from nature
48.
Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Trans Evol Comput 3(4):257–271CrossRef
49.
Zitzler E, Thiele L, Bader J (2008) SPAM: set preference algorithm for multiobjective optimization. In: Proceedings of international conference on parallel problem solving from nature
Metadaten
Titel
Evolutionary Multiobjective Optimization for the Pickup and Delivery Problem with Time Windows and Demands
verfasst von
Dũng H. Phan
Junichi Suzuki
Publikationsdatum
01.02.2016
Verlag
Springer US
Erschienen in
Mobile Networks and Applications / Ausgabe 1/2016
Print ISSN: 1383-469X
Elektronische ISSN: 1572-8153
DOI
https://doi.org/10.1007/s11036-016-0709-5

Weitere Artikel der Ausgabe 1/2016

Mobile Networks and Applications 1/2016 Zur Ausgabe

OriginalPaper

Exploring Social Networks and Improving Hypertext Results for Cloud Solutions

OriginalPaper

Social Networking Ontology Engineering Walkthrough: Practical Approach for Non-Expert User Learning

OriginalPaper

The Structural Role of Feed-Forward Loop Motif in Transcriptional Regulatory Networks

OriginalPaper

Two Fuzzy-Based Systems for Selection of Actor Nodes inWireless Sensor and Actor Networks: A Comparison Study Considering Security Parameter Effect

Erratum

Erratum to: Exploring Social Networks and Improving Hypertext Results for Cloud Solutions

OriginalPaper

Epistatic Signaling and Minority Games, the Adversarial Dynamics in Social Technological Systems

Neuer Inhalt

    Bildnachweise