The splitting delivery vehicle routing problem with 3-dimensional loading constraints (3L-SDVRP) is an important and challenging VRP variant. The problem consists of two subproblems: the routing and 3D bin packing, each of which is NP-hard by itself. Compared with CVRP, 3L-SDVRP is much closer to the reality. There have been many studies on 3L-SDVRP. However, to our best knowledge, no complete mathematical model has been formalised with comprehensive loading constraints and there are still some real-world factors ignored in the existing studies. In this paper, we consider a more realistic 3L-SDVRP model with restricted access provided by the 2021 HUAWEI Logistics Competition, which is different from existing problem models in two aspects. First, this problem considers the total travel cost and average loading rate simultaneously. Second, this problem has additional constraints related to certain special pickup points. These differences make existing optimisation approaches not directly applicable. A major contribution of this paper is the formal mathematical model developed for this new 3L-SDVRP. In addition, we propose a genetic algorithm with an efficient fitness evaluation. The proposed algorithm has been demonstrated to significantly outperform the baseline solver provided by the competition in solving the problem instances from the competition and the ones adapted from benchmark datasets of related problems. © 2021 IEEE.
|Title of host publication
|2021 IEEE Symposium Series on Computational Intelligence, SSCI 2021 - Proceedings
|Institute of Electrical and Electronics Engineers Inc.
|Published - 5 Dec 2021
Bibliographical noteThis work was supported by the National Natural Science Foundation of China (Grant No. 61906083), the Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Entrepreneurial Teams (Grant No. 2017ZT07X386), the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2021A1515011830), the Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531), the Shenzhen Fundamental Research Program (Grant No. JCYJ20190809121403553) and the Marsden Fund of New Zealand Government under Contract VUW1614.
- 3D packing
- Capacitated vehicle routing problem
- Combinatorial optimisation
- Splitting delivery