Electric Vehicle Pickup-and-Delivery Problem with Soft Time Windows, Partial Charging, and Uncertain Travel Time

Abstract

Electric vehicles (EVs) take advantage of reducing fossil-based environmental pollution and developing a more sustainable logistics network. Compared with internal combustion engine vehicles (ICEVs), EVs have new technical characteristics like limited battery capacity and long charging time at charging stations. With the diffusion of EVs, vehicle routing problems (VRPs) of EVs draw transportation service providers’ attention, which extends VRPs with intra-route charging considerations. In real-life practice, the punctuality of preplanned
vehicle routing may be affected by uncertain travel time caused by traffic congestion, which derives undesirable penalty costs for violating time windows. Besides, long intra-route charging time at charging stations presents an even greater challenge to trade-off between completing tours with enough electricity and providing delivery service on time. This assignment aims to investigate the impact of travel time uncertainty and electric vehicle characteristics on planning fleet size, vehicle routing, and charging schedules. A pickup and delivery
problem of electric vehicles is studied in this assignment, which considered flexible fleet size, partial charging policy, soft time windows and uncertain travel time. The problem is formulated as a two-stage stochastic linear programming model. The fleet size, vehicle routing, and charging decisions are determined in the first stage. After the realization of travel times, the second stage determines specific charging times at charging stations. The objective is to minimize the total operational cost, which consists of travel costs of vehicle usage and charging,
and the expected penalty cost of earliness, delay and overtime. The sample average approximation method is applied to model the stochastic programming to the deterministic equivalent and the Gurobi Optimizer is used to solve this mixed-integer programming. A computational experiment is conducted based on a small data set with one depot, 9 pickup and delivery requests, 5 charging stations at service vertices and 3 available electric trucks. The travel times along the delivery tour are assumed to follow Gamma distribution. To investigate the trade-off between travel costs and penalty costs, 12 instances are conducted in the experiment by tuning parameters of time windows, the uncertainty of travel time, and the importance of punctuality. The experiment results showed an increasing vehicle fleet size could improve the level of service but also derive more vehicle
usage costs. Besides, the intra-route charging operations impact vehicles’ departure times at each charging station, which subsequently impacts service start time at customer vertices. Longer intra-route charging time has the potential to enhance punctuality in instances with tight time windows or congested traffic conditions. Moreover, different operator inclination leads to different fleet size and charging time preference. Instances attaching more importance to punctuality have a larger fleet size and longer intra-route charging time.