# Route Planning for Autonomous Driving Based on Traffic Information via Multi-Objective Optimization
## 2 Literature Review  
Before presenting the description of the method in this paper, several existing methods are introduced. As discussed in Section 1, the goals of existing research can be roughly divided into the following optimization objectives: total travel distance, total travel time and total cost. After a careful review of the related work on the problem of route planning, it is found that most of the methods only rely on one of the factors or a combination of a few of them, which would indeed lead to a limitation of the route generation. Some of the typical route planning methods are chosen to be introduced below. 1. Total travel distance. In paper [21], a bilevel ant colony optimization algorithm for a capacitated electric vehicle routing problem is proposed. The vehicle routing problem is classified into two sub-problems: (1) capacitated vehicle routing problem and (2) fixed route vehicle charging problem. Assuming a set of the same vehicles, the goal of the vehicle routing problem in the research is to find an optimal route to minimize the total travel distance. The objective function of the algorithm is to minimize the total travel distance, which is defined as:  
\[min\quad f(x)=\sum_{i\in V,j\in V,i\
eq j}d_{ij}x_{ij} \tag{1}\]  
The constraints of the algorithm contain served times of customer, charging station limitations, capacity constraints, electricity constraint and domain definition. The proposed algorithm performed better than state-of-the-art algorithms in several real-world experiments. A bi-strategy-based optimization algorithm is derived to solve the dynamic vehicle routing problem in reference [22]. An effective scheduling generation scheme based on a permutation array, the k-nearest neighbor (kNN) heuristic based on the location information of customers for initialization and two search strategies for representation and scheduling are proposed. Similarly to the above research, a smaller total travel distance is supposed in this algorithm. 2. Total travel time. Paper [23] studies improved formulations and algorithmic components on the vehicle routing problem. An arc-based tracking of the time and the state of charge, which outperforms the classical node-based tracking of these values, is derived. A path-based model is proposed to avoid passing by the same station nodes. The objective function of the algorithm is to minimize the total driving and charging time, which is defined as:  
\[min\quad f(x)=\sum_{(i,j)\in A}t_{ij}x_{ij}+\sum_{i\in F}\delta_{i} \tag{2}\]  
where \(A\) is the set of travel arc, \(t_{ij}\) is the driving time on arc \((i,j)\) and \(\delta_{i}\) represents the charging time at node \(i\). The constraints of the algorithm contain served times of customer, the flow conservation, sufficient energy, limitation of charging time and departure time. Experiments show that taking the optimal or near-optimal charging decision is very important to produce high-quality solutions. Paper [24] builds a fuel consumption model related to travel time and calculates the fuel volume under different travel times through the nodes and edges of the transportation network and this method effectively balances the relationship between driving time and fuel consumption under different road traffic networks. Travel time is the optimization constraint of this algorithm. 3. Total cost. In the paper [25], an electric vehicle routing problem under time variant energy prices is addressed and a Lagrangian relaxation and a hybrid heuristic are proposed. The impact of energy prices, time windows and fleet size are considered in the study.