In recent years, the global shift toward sustainable transportation has accelerated the adoption of electric vehicles, particularly in regions like China where government policies and environmental concerns drive innovation. As a researcher focused on logistics and supply chain optimization, I have observed that the integration of electric vehicle into distribution networks presents unique challenges, especially when customer demands are complex and require discrete splitting into independent orders. This study addresses the electric vehicle routing problem by considering discrete split demands, where each customer’s requirement is divided into distinct, non-divisible orders, and optimizes charging strategies to minimize total costs, including fixed, routing, charging, and time-window penalty expenses. The electric vehicle, or China EV, market is rapidly expanding, and efficient logistics planning is crucial for reducing operational costs and enhancing service quality. By developing a multi-type electric vehicle model and an improved genetic-simulated annealing algorithm, this research aims to provide practical solutions for logistics enterprises operating in dynamic environments.
The problem involves a logistics company using various types of electric vehicle to serve customers distributed across a specific area. Each electric vehicle starts from a distribution center, delivers goods to multiple customer nodes, and returns to the center, all while adhering to time window constraints. A key aspect is the discrete splitting of customer demands into separate orders, which allows for flexible allocation to different vehicles, ensuring that no single vehicle is overloaded. However, the limited range of electric vehicle necessitates strategic charging at stations along the route. Two charging strategies are evaluated: partial charging, where vehicles charge only enough to complete subsequent tasks, and full charging, where batteries are replenished to maximum capacity. The electric vehicle routing optimization must account for these factors to achieve cost-effective and timely deliveries. This study formulates a mixed-integer programming model to capture these complexities and employs a hybrid algorithm to solve it efficiently, contributing to the growing body of knowledge on China EV applications in logistics.
To formalize the problem, let me define the sets, parameters, and decision variables. Let $O$ represent the distribution center, $N$ the set of customer nodes, $P$ the set of charging stations, and $K$ the set of electric vehicle available. The entire node set is $V = O \cup N \cup P$. For each customer node $i \in N$, the demand $p_i$ is split into discrete orders $r \in M_i$, with $pr_i$ denoting the demand of order $r$ at node $i$. Key parameters include $U_k$ for the load capacity of vehicle $k$, $Q_k$ for its battery capacity, $d_{ijk}$ for the distance traveled by vehicle $k$ from node $i$ to $j$, and $[e_i, l_i]$ for the time window at customer node $i$. The decision variables include $x_{ijk}$, a binary variable indicating if vehicle $k$ travels from $i$ to $j$; $y_{ik}$, indicating if vehicle $k$ visits node $i$; $w_{ijk}$, indicating if vehicle $k$ charges at station $j$ after leaving $i$; and $z_{ir}^k$, indicating if order $r$ at node $i$ is delivered by vehicle $k$.
The objective function minimizes the total cost, expressed as:
$$ \min Z = \sum_{j \in V} \sum_{k \in K} f_k x_{Ojk} + \sum_{i \in V} \sum_{j \in V} \sum_{k \in K} c_k d_{ijk} x_{ijk} + c_{ps} \sum_{i \in P} \sum_{k \in K} tc_{ik} + epu \sum_{i \in N} \sum_{k \in K} y_{ik} \max\{(e_i – t_{1ik}), 0\} + lpu \sum_{i \in N} \sum_{k \in K} y_{ik} \max\{(t_{1ik} – l_i), 0\} $$
where $f_k$ is the fixed cost of vehicle $k$, $c_k$ is the routing cost per km, $c_{ps}$ is the charging cost per hour, $epu$ and $lpu$ are early and late penalty costs, and $tc_{ik}$ is the charging time for vehicle $k$ at node $i$. The constraints ensure vehicle flow balance, demand satisfaction, capacity limits, and time window adherence. For instance, the demand constraint is:
$$ \sum_{k \in K} \sum_{r \in M_i} pr_i z_{ir}^k = p_i \quad \forall i \in N $$
and the load capacity constraint is:
$$ \sum_{i \in V} \sum_{r \in M_i} pr_i z_{ir}^k \leq U_k \quad \forall k \in K $$
For the charging strategies, the partial charging amount $F_{ijk}$ for vehicle $k$ moving from node $i$ to charging station $j$ is calculated based on the remaining energy required for subsequent deliveries:
$$ F_{ijk} = \begin{cases} r_{ijk} – q_{1jk}, & \text{if } r_{ijk} – q_{1jk} < Q_k \\ Q_k – q_{1jk}, & \text{otherwise} \end{cases} $$
where $r_{ijk}$ is the energy needed to complete the route after charging. In contrast, full charging sets $F_{ijk} = Q_k – q_{1jk}$. These strategies impact the overall cost and efficiency, as partial charging can reduce idle time and energy waste, making it particularly suitable for China EV operations where charging infrastructure may be congested.
The improved genetic-simulated annealing algorithm combines global and local search capabilities to handle the NP-hard nature of this electric vehicle routing problem. The genetic algorithm phase starts with population initialization using a scanning operator, which calculates polar coordinates relative to the distribution center to generate initial chromosomes. For example, the angle $\theta_i$ for each customer node $i$ is computed as:
$$ \theta_i = \arctan\left(\frac{y_i – y_0}{x_i – x_0}\right) $$
where $(x_0, y_0)$ is the center’s coordinates and $(x_i, y_i)$ is the node’s coordinates. The initial population is built by sorting these angles and creating routes, followed by random mutations to diversify the solutions. The fitness function is defined as the inverse of the total cost, encouraging the selection of cost-effective routes. Crossover and mutation operations are performed after removing charging station genes to avoid infeasible solutions, and then reinserting them based on energy requirements. For instance, if the remaining energy $q_{1jk}$ is insufficient, a charging station is added at the nearest point.
The simulated annealing phase refines the solutions by applying neighborhood operations, such as reversing segments of the chromosome, and using the Metropolis criterion to accept or reject new solutions. The temperature $T$ starts at an initial value $T_0$ and decreases by a cooling rate $hy$ until it reaches a termination temperature $T_{end}$. The probability of accepting a worse solution is $\exp(-\Delta Z / T)$, where $\Delta Z$ is the cost difference. This hybrid approach ensures robust optimization for large-scale instances, which is essential for real-world China EV logistics applications.
To validate the model and algorithm, I conducted computational experiments using both small-scale and large-scale instances. For small-scale cases, based on Solomon’s R101 dataset, I tested with 6, 8, 12, and 16 customer nodes, each with 2 orders and 2 charging stations. Two types of electric vehicle were used: Type C1 with a load capacity of 1 ton and battery capacity of 130 kWh, and Type C2 with 1.5 tons and 160 kWh. The parameters included a fixed cost of 600 and 800 units, routing cost of 8 and 10 units per km, charging cost of 50 units per hour, and time window penalties of 10 and 20 units per hour for early and late arrivals, respectively. The results compared CPLEX and the proposed algorithm, as shown in the table below.
| Instance | CPLEX Optimal Cost | Proposed Algorithm Cost | Gap (%) | Runtime (s) |
|---|---|---|---|---|
| p-6 | 537.45 | 537.45 | 0 | 3.25 |
| p-8 | 606.58 | 606.58 | 0 | 3.86 |
| p-12 | 736.26 | 738.69 | 0.33 | 5.23 |
| p-16 | 906.54 | 953.76 | 0.52 | 6.59 |
The algorithm achieved near-optimal solutions with significantly shorter runtimes, demonstrating its efficiency for electric vehicle routing problems. In the large-scale instance with 32 customer nodes and 5 charging stations, the electric vehicle types were the same, with a maximum of 8 vehicles per type. Customer demands were randomly split into 1–3 orders, and the algorithm optimized routes under both charging strategies. The partial charging strategy resulted in lower costs, as summarized in the following table.
| Charging Strategy | Routing Cost | Charging Cost | Penalty Cost | Total Cost |
|---|---|---|---|---|
| Partial | 828.20 | 54.27 | 314.08 | 2091.18 |
| Full | 981.37 | 67.69 | 356.70 | 2310.15 |
Partial charging reduced total cost by 218.97 units, highlighting its economic advantages for China EV logistics. The charging rates for partial charging ranged from 25% to 43.9%, minimizing charging time and energy waste. For example, the energy dynamics for a vehicle $k$ can be modeled as:
$$ q_{2ik} = q_{1ik} – h \cdot d_{ijk} \cdot x_{ijk} + w_{ijk} F_{ijk} $$
where $h$ is the energy consumption coefficient. This approach ensures that electric vehicle operate efficiently within their constraints.
Sensitivity analysis examined the impact of charging waiting times on time window penalty costs. As waiting times increased from 0.3 to 1.2 hours, both strategies saw rising penalties, but partial charging showed a slower growth rate. For instance, at 1.2 hours, the penalty cost for partial charging was approximately 15 units lower than for full charging, as illustrated by the trend:
$$ \Delta \text{Penalty} = \text{Penalty}_{\text{full}} – \text{Penalty}_{\text{partial}} $$
This makes partial charging more suitable for scenarios with prolonged waiting times, common in urban China EV networks where charging stations may be busy. The analysis underscores the importance of adaptive charging strategies in minimizing costs and improving service reliability.
In conclusion, this study addresses the critical challenge of optimizing electric vehicle routing with discrete split demands, a relevant issue for the expanding China EV market. The proposed model and algorithm effectively reduce costs while accommodating complex logistics constraints. Partial charging emerges as a superior strategy, offering significant savings and flexibility, especially under variable charging conditions. Future work could explore dynamic routing adjustments and integration with renewable energy sources to further enhance the sustainability of electric vehicle logistics. As electric vehicle continue to evolve, such optimizations will play a pivotal role in shaping efficient and eco-friendly supply chains.