Towards Efficient and Electrified Road Transport: Itinerary and Infrastructure Planning


Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date9 Jun 2020


Intelligent transportation system (ITS) aims to facilitate a better use of road networks in terms of efficiency, safety and reliability, by integrating various advanced technologies with transport engineering. With the electrification of road transport systems in recent years, ITS has been continuously evolving to overcome the drawbacks of electric vehicles (EVs), such as the limited driving range and long re-charge time. Among all the practical issues under the scope of ITS, this thesis focuses on two fundamental ones, namely the planning of vehicle’s itinerary and supportive infrastructures. Based on mathematical modeling and optimization techniques, a variety of state-of-art problems are addressed with some efficient solution algorithms proposed.

Firstly, we consider the multi-depot vehicle routing problem (MDVRP) commonly found in logistics industry. The MDVRP is to deliver goods from a set of depots to customers in an efficient way. In this particular MDVRP variant, customer service time is also considered. To solve this problem, a hybrid multi-objective evolutionary algorithm (HMOEA) is designed. As illustrated by simulation results, HOMEA outperforms other methods in terms of both convergence and diversity, thanks to a new initialization process and an ordered version of cut-and-paste operator inspired by jumping gene genetic algorithm (JGGA), together with other local search operators.

Undoubtedly, the upcoming large-scale deployment of EVs would lead to dramatic changes in the operation and management of road transport. Therefore, routing problems in distribution logistics need to be reformulated: a dynamic electric vehicle routing problem (D-EVRP) model based on a finite-horizon Markov decision process (MDP) is thus developed. It aims to minimize the overall service duration of an EV, e.g. electric van, for goods distribution. To better reflect the real situation, the road network is associated with time-dependent stochastic traffics while the EV energy dynamics are characterized by a generic battery model. Since the classic stochastic dynamic programming (SDP) approaches suffer from curse of dimensionality, an efficient hybrid rollout algorithm (HRA) is designed. Simulation results also confirm the significance of the use of analytical battery model in this class of problems.

In distribution logistics, electric trucks are usually deployed for long-distance delivery, e.g. interstate delivery. Instead of traversing a whole set of customers’ locations as in the D-EVRP, the itinerary planning for an electric truck, or more generally, any EV traveling from an origin to a distant destination, is more of a variant for the classic shortest path problem. The difference is that, when the path length exceeds its driving range, the EV needs to visit a (selection of) charging station(s) before arriving at the destination. We manage such en-route re-charge activities of EVs with an optimization framework, which is to collectively distribute EV flows with the consideration of queuing (for re-charge) at charging stations. A two-stage flow distribution algorithm (FDA) is then devised as the solver and its effectiveness is analyzed with different charging infrastructure settings. It is concluded that a proportional allocation of chargers to nodes with high weighted betweenness contributes the most efficient flow distribution solution, as compared to other nodal-centrality based allocations. Although this scheme performs slightly worse than an optimization-based one, it provides a better balance between efficiency and robustness, which are revealed to be two conflicting features of the flow distribution solutions.

Lastly, we extend the EV flow distribution model to incorporate the impact of stochastic traffic conditions. To magnify the positive impact of the interdependence between EV flow distribution and charging resource allocation, the coordination between these two decision-makings is characterized by a two-stage stochastic programming formulation. Based on sample average approximation (SAA) and constraint relaxation, a feasible deterministic equivalent of the original problem is derived and solved by joint optimization, which includes a standard convex solver and a meta-heuristic method. Simulation results justify the quality of the deterministic solutions and the out-performance of the proposed algorithm. The obtained solution not only provides a high-quality charger allocation, but also a collection of optimal EV flow distribution policies under any traffic conditions. Moreover, a lower bound for the number of chargers to be allocated can be estimated, which is useful to prevent the over-allocation of charging resources.