Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost

Yong WANG^a,b,*, Maozeng XU^a,*, Yong Liu^a

(^aSchool of Economics and Management, Chongqing Jiaotong University, Chongqing 400074, China)

(^bSchool of Management and Economics, University of Electronic Science and Technology, Chengdu 610054, China)

E-mail: yongwx6@gmail.com^*; xmzzrxhy@cqjtu.edu.cn^*; liuevery@gmail.com; 

^*Corresponding author

Abstract: The control of the environmental impacts is a considerable challenge to the daily operations of modern logistics companies, especially under the current trend of increasing carbon dioxide emission. This paper focusses on freight distribution, introduces a transportation resource sharing strategy to address the multi-depot green vehicle routing problem, and incorporates the time-dependency of speed as well as piecewise penalty costs for earliness and tardiness of deliveries. Transportation resource sharing is proposed to eliminate long and empty-vehicle trips, improve the network’s fluidity and the efficiency of resource management. A bi-objective model is proposed to minimize total carbon emission and operating cost, while enforcing piecewise penalty costs on earliness and tardiness to reduce waiting time and improve customer satisfaction. Further, we combine the Clarke and Wright Savings Heuristic Algorithm (CWSHA), the Sweep Algorithm (SwA) and the Multi-Objective Particle Swarm Optimization algorithm (MOPSO) to design a hybrid heuristic algorithm for the vehicle routing optimization. CWSHA and SwA are consecutively used to generate the initial population, and MOPSO is employed for local and global solution search. Computational experiments reveal that sharing transportation resource reduces the total travelled distance, the number of vehicles, and facilitates a cost effective and environment-friendly distribution network. In addition, we also observe thatthe shortest path sometimes undermines minimum cost and carbon emission objectives. Moreover,sensitivity analyses reveal that vehicle routes are less influenced by piecewise penalty costs under unimodal traffic flows, while bimodal traffic flows would require more investment to reduce carbon emission.

Keywords:Green vehicle routing; Resource sharing; Time-dependent vehicle speed; Piecewise penalty cost; Hybrid heuristic

1.        Introduction

Climate change is one of the current topics at the heart of many international development programs, and the reduction of carbon dioxide (CO₂) emission is one of the solutions which attract extensive attention from policy makers and researchers. CO₂emission has increased by approximately 50 percent since 1990 (UNDP, 2015), especially between January 2016 and January 2017 where the second largest annual increase since 1980 was recorded (U.S. NOAA, 2017). With regards to the resulting environmental challenges, several approaches such as installing industrial zones outside cities and encouraging greener areas within cities are being implemented by a large number of local governments and practitioners. Meanwhile in literature, some researchers frequently concentrate on the optimization of road freight transportation which constitutes one of the growing carbon dioxide emission sources (Tang et al., 2013; Salehi et al., 2017; Zuo et al. 2018). Among other factors, the quantity of emitted CO₂is related to fuel consumption, which is influenced by factors like speed, distance, weight, road gradient, vehicle shape, air density, etc. While distance, weight, and shape parameters may remain constant for a homogeneous transportation fleet on the same road, speed usually varies depending on drivers, time, roads condition, etc. 

This paper approaches the environmental challenges faced by road freight transportation operators from a collaborative aspect, and includes vehicle sharing to propose a systematic optimization method. Without loss of generality, we assume that drivers possess the same features and roads are in good condition. Considering the time-dependency of speed, we reflect real-world operations through morning and evening traffic peaks modeling. Nevertheless, free-flow traffics are also considered, though they may not always guarantee on-time delivery because driving faster may also lead to earliness. The existence of such nuance hardens decision making on the design of environment-friendly distribution networks, as well as the elaboration of strategies for their sustainability.