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
Mobile Networks and Applications
Published in: Mobile Networks and Applications 1/2016

01-02-2016

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

Authors: Dũng H. Phan, Junichi Suzuki

Published in: Mobile Networks and Applications | Issue 1/2016

Log in

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

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.
previous article Epistatic Signaling and Minority Games, the Adversarial Dynamics in Social Technological Systems
next article The Structural Role of Feed-Forward Loop Motif in Transcriptional Regulatory Networks

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
Show more products
Footnotes
Literature
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.
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
Metadata
Title
Evolutionary Multiobjective Optimization for the Pickup and Delivery Problem with Time Windows and Demands
Authors
Dũng H. Phan
Junichi Suzuki
Publication date
01-02-2016
Publisher
Springer US
Published in
Mobile Networks and Applications / Issue 1/2016
Print ISSN: 1383-469X
Electronic ISSN: 1572-8153
DOI
https://doi.org/10.1007/s11036-016-0709-5

Other articles of this Issue 1/2016

Mobile Networks and Applications 1/2016 Go to the issue

OriginalPaper

Autonomous Ant-based Public Key Authentication Mechanism for Mobile Ad-hoc Networks

OriginalPaper

Base Station Location -Aware Optimization Model of the Lifetime of Wireless Sensor Networks

OriginalPaper

An Ontology-Based Multi-Agent System for Active Software Engineering Ontology

OriginalPaper

Dependable Traffic Control Strategies for Urban and Freeway Networks

OriginalPaper

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

OriginalPaper

Bioinspired Security Analysis of Wireless Protocols