A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 7 Issue 4
Jun.  2020

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2020  >  7(4): 1134-1153
Jiahai Wang, Yuyan Sun, Zizhen Zhang and Shangce Gao, "Solving Multitrip Pickup and Delivery Problem With Time Windows and Manpower Planning Using Multiobjective Algorithms," IEEE/CAA J. Autom. Sinica, vol. 7, no. 4, pp. 1134-1153, July 2020. doi: 10.1109/JAS.2020.1003204
Citation: Jiahai Wang, Yuyan Sun, Zizhen Zhang and Shangce Gao, "Solving Multitrip Pickup and Delivery Problem With Time Windows and Manpower Planning Using Multiobjective Algorithms," IEEE/CAA J. Autom. Sinica, vol. 7, no. 4, pp. 1134-1153, July 2020. doi: 10.1109/JAS.2020.1003204
shu

Solving Multitrip Pickup and Delivery Problem With Time Windows and Manpower Planning Using Multiobjective Algorithms

doi: 10.1109/JAS.2020.1003204
Funds:  This work was supported by the National Key R&D Program of China (2018AAA0101203), the National Natural Science Foundation of China (61673403, 71601191), and the JSPS KAKENHI (JP17K12751)
More Information
    Abstract
  • 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.

     

    • FullText(HTML)
  • loading
    • References(43)
  • [1]
    L. Wang and J. Lu, “A memetic algorithm with competition for the capacitated green vehicle routing problem,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 2, pp. 516–526, 2019. doi: 10.1109/JAS.2019.1911405
    [2]
    J. Wang, L. Yuan, Z. Zhang, S. Gao, Y. Sun, and Y. Zhou, “Multiobjective multiple neighborhood search algorithms for multiobjective fleet size and mix location-routing problem with time windows,” IEEE Trans. Systems,Man,and Cybernetics:Systems, 2019. doi: 10.1109/TSMC.2019.2912194
    [3]
    J. Wang, T. Weng, and Q. Zhang, “A two-stage multiobjective evolutionary algorithm for multiobjective multi-depot vehicle routing problem with time windows,” IEEE Trans. Cybernetics, vol. 49, no. 7, pp. 2467–2478, 2019. doi: 10.1109/TCYB.2018.2821180
    [4]
    J. Wang, Y. Zhou, Y. Wang, J. Zhang, C. P. Chen, and Z. Zheng, “Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: formulation, instances and algorithms,” IEEE Trans. Cybernetics, vol. 46, no. 3, pp. 582–594, 2016. doi: 10.1109/TCYB.2015.2409837
    [5]
    G. Kim, Y.-S. Ong, C. K. Heng, P. S. Tan, and N. A. Zhang, “City vehicle routing problem (city VRP): A review,” IEEE Trans. Intelligent Transportation Systems, vol. 16, no. 4, pp. 1654–1666, 2015. doi: 10.1109/TITS.2015.2395536
    [6]
    U. Derigs and M. Pullmann, “A computational study comparing different multiple neighbourhood strategies for solving rich vehicle routing problems,” IMA J. Management Mathematics, vol. 27, no. 1, pp. 3–23, 2016. doi: 10.1093/imaman/dpt022
    [7]
    T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows,” Computers&Operations Research, vol. 40, no. 1, pp. 475–489, 2013.
    [8]
    T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, “A unified solution framework for multi-attribute vehicle routing problems,” European J. Operational Research, vol. 234, no. 3, pp. 658–673, 2014. doi: 10.1016/j.ejor.2013.09.045
    [9]
    A. Lim, Z. Zhang, and H. Qin, “Pickup and delivery service with manpower planning in Hong Kong public hospitals,” Transportation Science, vol. 51, no. 2, pp. 688–705, 2016.
    [10]
    Z. Zhang, H. Qin, K. Wang, H. He, and T. Liu, “Manpower allocation and vehicle routing problem in non-emergency ambulance transfer service,” Transportation Research Part E, vol. 106, pp. 45–59, 2017. doi: 10.1016/j.tre.2017.08.002
    [11]
    Y. Cai, Z. Zhang, S. Guo, H. Qin, and A. Lim, “A tree-based tabu search for the manpower allocation problem with time windows and job-teaming constraints,” in Proc. 23rd Int. Joint Conf. Artificial Intelligence, 2013, pp. 496–502.
    [12]
    Y. Yu, S. Gao, Y. Wang, and Y. Todo, “Global optimum-based search differential evolution,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 2, pp. 379–394, 2019. doi: 10.1109/JAS.2019.1911378
    [13]
    M. A. Nayeem, M. M. Islam, and X. Yao, “Solving transit network design problem using many-objective evolutionary approach,” IEEE Trans. Intelligent Transportation Systems, vol. 20, no. 10, pp. 3952–3963, 2019. doi: 10.1109/TITS.2018.2883511
    [14]
    A. Gupta, C. K. Heng, Y.-S. Ong, P. S. Tan, and A. N. Zhang, “A generic framework for multi-criteria decision support in eco-friendly urban logistics systems,” Expert Systems With Applications, vol. 71, pp. 288–300, 2017. doi: 10.1016/j.eswa.2016.09.033
    [15]
    A. Zhou, B.-Y. Qu, H. Li, S.-Z. Zhao, P. N. Suganthan, and Q. Zhang, “Multiobjective evolutionary algorithms: A survey of the state of the art,” Swarm and Evolutionary Computation, vol. 1, no. 1, pp. 32–49, 2011. doi: 10.1016/j.swevo.2011.03.001
    [16]
    A. Blot, M.-É. Kessaci, and L. Jourdan, “Survey and unification of local search techniques in metaheuristics for multi-objective combinatorial optimisation,” J. Heuristics, vol. 24, no. 6, pp. 853–877, 2018. doi: 10.1007/s10732-018-9381-1
    [17]
    Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Trans. Evolutionary Computation, vol. 11, no. 6, pp. 712–731, 2007. doi: 10.1109/TEVC.2007.892759
    [18]
    K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002. doi: 10.1109/4235.996017
    [19]
    M. Diana and M. M. Dessouky, “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows,” Transportation Research Part B:Methodological, vol. 38, no. 6, pp. 539–557, 2004. doi: 10.1016/j.trb.2003.07.001
    [20]
    F. Arnold and K. Sörensen, “Knowledge-guided local search for the vehicle routing problem,” Computers&Operations Research, vol. 105, pp. 32–46, 2019.
    [21]
    S. Abdullah and H. Turabieh, “On the use of multi neighbourhood structures within a tabu-based memetic approach to university timetabling problems,” Information Sciences, vol. 191, pp. 146–168, 2012. doi: 10.1016/j.ins.2011.12.018
    [22]
    H. Ishibuchi, Y. Hitotsuyanagi, N. Tsukamoto, and Y. Nojima, “Use of heuristic local search for single-objective optimization in multiobjective memetic algorithms,” in Proc. Int. Conf. Parallel Problem Solving from Nature. Springer, 2008, pp. 743–752.
    [23]
    O. Bräysy and M. Gendreau, “Vehicle routing problem with time windows, part I: Route construction and local search algorithms,” Transportation Science, vol. 39, no. 1, pp. 104–118, 2005. doi: 10.1287/trsc.1030.0056
    [24]
    E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu, “Hyper-heuristics: A survey of the state of the art,” J. Operational Research Society, vol. 64, no. 12, pp. 1695–1724, 2013. doi: 10.1057/jors.2013.71
    [25]
    N. Pillay and R. Qu, Hyper-Heuristics: Theory and Applications, Natural Computing Series. Springer, 2018.
    [26]
    N. Hitomi and D. Selva, “A classification and comparison of credit assignment strategies in multiobjective adaptive operator selection,” IEEE Trans. Evolutionary Computation, vol. 21, no. 2, pp. 294–314, 2017. doi: 10.1109/TEVC.2016.2602348
    [27]
    W. Hu and G. G. Yen, “Adaptive multiobjective particle swarm optimization based on parallel cell coordinate system,” IEEE Trans. Evolutionary Computation, vol. 19, no. 1, pp. 1–18, 2015. doi: 10.1109/TEVC.2013.2296151
    [28]
    I. Das and J. E. Dennis, “Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems,” SIAM J. Optimization, vol. 8, no. 3, pp. 631–657, 1998. doi: 10.1137/S1052623496307510
    [29]
    F. Wilcoxon, “Individual comparisons by ranking methods,” Biometrics Bulletin, vol. 1, no. 6, pp. 80–83, 1945. doi: 10.2307/3001968
    [30]
    J. Derrac, S. García, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms,” Swarm and Evolutionary Computation, vol. 1, no. 1, pp. 3–18, 2011. doi: 10.1016/j.swevo.2011.02.002
    [31]
    J. Alcalá-Fdez, L. Sánchez, S. García, M. del Jesus, S. Ventura, J. Garrell, J. Otero, C. Romero, J. Bacardit, V. Rivas, J. Fernández, and F. Haerrera, “KEEL: A software tool to assess evolutionary algorithms for data mining problems,” Soft Computing, vol. 13, no. 3, pp. 307–318, 2009. doi: 10.1007/s00500-008-0323-y
    [32]
    Y. Mei, K. Tang, and X. Yao, “Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem,” IEEE Trans. Evolutionary Computation, vol. 15, no. 2, pp. 151–165, 2011. doi: 10.1109/TEVC.2010.2051446
    [33]
    R. L. Pinheiro, D. Landa-Silva, and J. Atkin, “A technique based on trade-off maps to visualise and analyse relationships between objectives in optimisation problems,” J. Multi-Criteria Decision Analysis, vol. 24, no. 1-2, pp. 37–56, 2017. doi: 10.1002/mcda.1604
    [34]
    R. L. Pinheiro, D. Landa-Silva, W. Laesanklang, and A. A. Constantino, “An efficient application of goal programming to tackle multiobjective problems with recurring fitness landscapes,” in Proc. 7th Int. Conf. Operations Research and Enterprise Systems, 2018.
    [35]
    Z. Zhang, Y. Sun, H. Xie, Y. Teng, and J. Wang, “GMMA: GPU based multiobjective memetic algorithms for vehicle routing problem with route balancing,” Applied Intelligence, vol. 49, no. 1, pp. 63–78, 2019. doi: 10.1007/s10489-018-1210-6
    [36]
    Y. Xu and R. Qu, “Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighbourhoods,” J. Operational Research Society, vol. 62, no. 2, pp. 313–325, 2011. doi: 10.1057/jors.2010.138
    [37]
    H. Li and D. Landa-Silva, “An adaptive evolutionary multi-objective approach based on simulated annealing,” Evolutionary Computation, vol. 19, no. 4, pp. 561–595, 2011. doi: 10.1162/EVCO_a_00038
    [38]
    E. Burke and J. Landa Silva, “The influence of the fitness evaluation method on the performance of multiobjective search algorithms,” European J. Operational Research, vol. 169, no. 3, pp. 875–897, 2006. doi: 10.1016/j.ejor.2004.08.028
    [39]
    L. Ke, Q. Zhang, and R. Battiti, “Hybridization of decomposition and local search for multiobjective optimization,” IEEE Trans. Cybernetics, vol. 44, no. 10, pp. 1808–1820, 2014. doi: 10.1109/TCYB.2013.2295886
    [40]
    B. Derbel, A. Liefooghe, Q. Zhang, H. Aguirre, and K. Tanaka, “Multi-objective local search based on decomposition,” Lecture Notes in Computer Science, vol. 9921 LNCS, pp. 431–441, 2016. doi: 10.1007/978-3-319-45823-6_40
    [41]
    J. Shi, Q. Zhang, and J. Sun, “PPLS/D: Parallel Pareto local search based on decomposition,” IEEE Trans. Cybernetics, vol. 50, no. 3, pp. 1068–1071, 2020.
    [42]
    J. Wang and T. Kumbasar, “Parameter optimization of interval type-2 fuzzy neural networks based on PSO and BBBC methods,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 1, pp. 247–257, 2019. doi: 10.1109/JAS.2019.1911348
    [43]
    S. Gao, M. Zhou, Y. Wang, J. Cheng, H. Yachi, and J. Wang, “Dendritic neural model with effective learning algorithms for classification, approximation, and prediction,” IEEE Trans. Neural Networks and Learning Systems, vol. 30, no. 2, pp. 601–604, 2019. doi: 10.1109/TNNLS.2018.2846646
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(9)  / Tables(7)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1083) PDF downloads(73) Cited by()

    Highlights

    • A multiobjective pickup and delivery problem with time windows and manpower planning is introduced.
    • A multiobjective iterated local search algorithm with adaptive neighborhood is proposed.
    • The nature of objective functions and the properties of the problem are analyzed.
    • The benefits of multiobjective optimization are discussed.

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return