Solving multitrip pickup and delivery problem with time windows and manpower planning using multiobjective algorithms

被引：66
作者：
Wang, Jiahai [1 ,2 ,3 ]
Sun, Yuyan [1 ]
Zhang, Zizhen [1 ]
Gao, Shangce [4 ]
机构：
[1] Sun Yat Sen Univ, Dept Comp Sci, Guangzhou 510275, Peoples R China
[2] Sun Yat Sen Univ, Minist Educ, Key Lab Machine Intelligence & Adv Comp, Guangzhou 510275, Peoples R China
[3] Sun Yat Sen Univ, Guangdong Key Lab Big Data Anal & Proc, Guangzhou 510275, Peoples R China
[4] Univ Toyama, Fac Engn, Toyama 9308555, Japan
来源：
IEEE-CAA JOURNAL OF AUTOMATICA SINICA | 2020年 / 7卷 / 04期
基金：
中国国家自然科学基金; 国家重点研发计划;
关键词：
Adaptive neighborhood selection; manpower planning; multiobjective optimization; multitrip; pickup and delivery problem with time windows; VEHICLE-ROUTING PROBLEM; LOCAL SEARCH; EVOLUTIONARY ALGORITHMS; OPTIMIZATION; FRAMEWORK;
D O I：
10.1109/JAS.2020.1003204
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The multitrip pickup and delivery problem with time windows and manpower planning (MTPDPTW-MP) determines a set of ambulance routes and finds staff assignment for a hospital. It involves different stakeholders with diverse interests and objectives. This study firstly introduces a multiobjective MTPDPTW-MP (MO-MTPDPTWMP) with three objectives to better describe the real-world scenario. A multiobjective iterated local search algorithm with adaptive neighborhood selection (MOILS-ANS) is proposed to solve the problem. MOILS-ANS can generate a diverse set of alternative solutions for decision makers to meet their requirements. To better explore the search space, problem-specific neighborhood structures and an adaptive neighborhood selection strategy are carefully designed in MOILS-ANS. Experimental results show that the proposed MOILS-ANS significantly outperforms the other two multiobjective algorithms. Besides, the nature of objective functions and the properties of the problem are analyzed. Finally, the proposed MOILS-ANS is compared with the previous single-objective algorithm and the benefits of multiobjective optimization are discussed.
引用
收藏
页码：1134 / 1153
页数：20
相关论文
共 43 条
[1]   On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems [J].
Abdullah, Salwani ;
Turabieh, Hamza .
INFORMATION SCIENCES, 2012, 191 :146-168
[2]   KEEL: a software tool to assess evolutionary algorithms for data mining problems [J].
Alcala-Fdez, J. ;
Sanchez, L. ;
Garcia, S. ;
del Jesus, M. J. ;
Ventura, S. ;
Garrell, J. M. ;
Otero, J. ;
Romero, C. ;
Bacardit, J. ;
Rivas, V. M. ;
Fernandez, J. C. ;
Herrera, F. .
SOFT COMPUTING, 2009, 13 (03) :307-318
[3]   Knowledge-guided local search for the vehicle routing problem [J].
Arnold, Florian ;
Sorensen, Kenneth .
COMPUTERS & OPERATIONS RESEARCH, 2019, 105 :32-46
[4]   Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation [J].
Blot, Aymeric ;
Kessaci, Marie-Eleonore ;
Jourdan, Laetitia .
JOURNAL OF HEURISTICS, 2018, 24 (06) :853-877
[5]   Vehicle routing problem with time windows, part 1:: Route construction and local search algorithms [J].
Bräysy, I ;
Gendreau, M .
TRANSPORTATION SCIENCE, 2005, 39 (01) :104-118
[6]   Hyper-heuristics: a survey of the state of the art [J].
Burke, Edmund K. ;
Gendreau, Michel ;
Hyde, Matthew ;
Kendall, Graham ;
Ochoa, Gabriela ;
Oezcan, Ender ;
Qu, Rong .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2013, 64 (12) :1695-1724
[7]   The influence of the fitness evaluation method on the performance of multiobjective search algorithms [J].
Burke, EK ;
Silva, JDL .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 169 (03) :875-897
[8]  
Cai Y., 2013, P 23 INT JOINT C ART, P496
[9]   Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems [J].
Das, I ;
Dennis, JE .
SIAM JOURNAL ON OPTIMIZATION, 1998, 8 (03) :631-657
[10]   A fast and elitist multiobjective genetic algorithm: NSGA-II [J].
Deb, K ;
Pratap, A ;
Agarwal, S ;
Meyarivan, T .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2002, 6 (02) :182-197
12345