Bi-Objective Splitting Delivery VRP with Loading Constraints and Restricted Access

Jiyuan PEI; Chengpeng HU; Jialin LIU; Yi MEI; Xin YAO

doi:10.1109/SSCI50451.2021.9659967

Bi-Objective Splitting Delivery VRP with Loading Constraints and Restricted Access

Jiyuan PEI, Chengpeng HU, Jialin LIU, Yi MEI, Xin YAO

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

5 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	2021 IEEE Symposium Series on Computational Intelligence, SSCI 2021 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Print)	9781728190488
DOIs	https://doi.org/10.1109/SSCI50451.2021.9659967
Publication status	Published - 5 Dec 2021
Externally published	Yes

Funding

This 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.

Keywords

3D packing
3L-SDVRP
Capacitated vehicle routing problem
Combinatorial optimisation
Splitting delivery

Access to Document

10.1109/SSCI50451.2021.9659967

Cite this

@inproceedings{411cd76c5c954ce2802a81c8296db0f9,

title = "Bi-Objective Splitting Delivery VRP with Loading Constraints and Restricted Access",

abstract = "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. {\textcopyright} 2021 IEEE.",

keywords = "3D packing, 3L-SDVRP, Capacitated vehicle routing problem, Combinatorial optimisation, Splitting delivery",

author = "Jiyuan PEI and Chengpeng HU and Jialin LIU and Yi MEI and Xin YAO",

year = "2021",

month = dec,

day = "5",

doi = "10.1109/SSCI50451.2021.9659967",

language = "English",

isbn = "9781728190488",

booktitle = "2021 IEEE Symposium Series on Computational Intelligence, SSCI 2021 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

Bi-Objective Splitting Delivery VRP with Loading Constraints and Restricted Access. / PEI, Jiyuan; HU, Chengpeng; LIU, Jialin et al.
2021 IEEE Symposium Series on Computational Intelligence, SSCI 2021 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2021.

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

T1 - Bi-Objective Splitting Delivery VRP with Loading Constraints and Restricted Access

AU - PEI, Jiyuan

AU - HU, Chengpeng

AU - LIU, Jialin

AU - MEI, Yi

AU - YAO, Xin

PY - 2021/12/5

Y1 - 2021/12/5

N2 - 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.

AB - 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.

KW - 3D packing

KW - 3L-SDVRP

KW - Capacitated vehicle routing problem

KW - Combinatorial optimisation

KW - Splitting delivery

UR - http://www.scopus.com/inward/record.url?scp=85125788960&partnerID=8YFLogxK

U2 - 10.1109/SSCI50451.2021.9659967

DO - 10.1109/SSCI50451.2021.9659967

M3 - Conference paper (refereed)

SN - 9781728190488

BT - 2021 IEEE Symposium Series on Computational Intelligence, SSCI 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Bi-Objective Splitting Delivery VRP with Loading Constraints and Restricted Access

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this