Skip to content

Latest commit

 

History

History
218 lines (177 loc) · 7.29 KB

README.md

File metadata and controls

218 lines (177 loc) · 7.29 KB
Raw

EVRP-TW-SPD

Overview

The dataset and unofficial CPLEX code for the Electric Vehicle Routing Problem with Time Windows, Simultaneous Pickup and Deliveries (EVRP-TW-SPD), based on the paper "Application of CMSA to the Electric Vehicle Routing Problem with Time Windows, Simultaneous Pickup and Deliveries, and Partial Vehicle Charging" (Akbay et al., 2022), have been reimplemented here.

The official EVRP-TW-SPD instances used in Akbay et al. (2022) can be found at EVRP-TW-SPD-Instances.

File Structure

EVRP-TW-SPD/
│
├── README.md                   # overview
│
├── src/                        # CPLEX code (unofficial)
│   ├── EVRP-TW-SPD.mod         # EVRP-TW-SPD MILP .mod file 
│   ├── EVRP-TW-SPD.ops         # specific CPLEX optimization settings .ops file (not optimal)
│   ├── cplex_evrptwspd         # CPLEX input data .dat files
│   └── ...  
│
├── data/                       # datasets (official)
│   ├── evrptwspd_instances     # the EVRP-TW-SPD dataset used in Akbay et al. (2022)
│   ├── evrptw_instances        # the E-VRPTW dataset used in Schneider et al. (2014)
│   └── ...
│
├── CITATION.cff
└── LICENSE

We generated the EVRP-TW-SPD dataset and performed CPLEX 20.1 verification.

Dataset Generation

As stated in the paper by Akbay et al. (2022), the EVRP-TW-SPD dataset they used was generated based on the E-VRPTW problem instances introduced in the paper "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations" (Schneider et al., 2014), where the delivery demand of each customer was divided into separate delivery and pickup demands using the approach from the paper "A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling" (Salhi et al., 1999).

Note that when calculating the separated delivery value, Akbay et al. (2022) automatically reserved the integer part by truncating the decimal part. We followed the details of their dataset generation process; thus, the EVRP-TW-SPD dataset generated in our repository should match the official EVRP-TW-SPD instances presented in Akbay et al. (2022).

The EVRP-TW-SPD dataset instance generator evrptwspd_instances_generator.py was implemented in Python.

Verification

To verify the correctness of the EVRP-TW-SPD dataset generation, we provide unofficial CPLEX code to compare results with the corresponding numerical results in the paper by Akbay et al. (2022), as their CPLEX code is not open-sourced.

For simplicity, this CPLEX code is based on E-VRPTW, where we set three dummy vertices for each charging station in the .dat files. However, the .ops file is not exactly the same as in the paper by Akbay et al. (2022).

Experiments were performed on a personal computer with an 11th Gen Intel® Core™ i5-1135G7 CPU, which has 8 cores operating at 2.40 GHz, and a minimum of 16 GB of RAM.

Computational results of CPLEX 20.1 on small-scale instances with five customers

Instances name CPLEX 20.1 numerical results in paper (Akbay et al., 2022) CPLEX 20.1 numerical results in verification gap(%)
m best time m best time
c101C5 2 2257.75 0.61 2 2257.75 4.62 0.00
c103C5 1 1175.37 0.58 1 1175.37 1.24 0.00
c206C5 1 1242.56 0.82 1 1242.56 114.26 0.00
c208C5 1 1158.48 0.12 1 1158.48 1.03 0.00
r104C5 2 2136.69 0.03 2 2136.69 1.67 0.00
r105C5 2 2156.08 0.04 2 2156.08 0.90 0.00
r202C5 1 1128.78 0.08 1 1128.78 1.16 0.00
r203C5 1 1179.06 0.04 1 1179.06 1.32 0.00
rc105C5 2 2233.77 3.10 2 2233.77 6.51 0.00
rc108C5 2 2253.93 0.27 2 2253.93 6.04 0.00
rc204C5 1 1176.39 0.36 1 1176.39 12.41 0.00
rc208C5 1 1167.98 0.17 1 1167.98 1.13 0.00

where m denotes the vehicle number, best represents the optimal objective values, time indicates the total runtime in seconds, and gap is calculated as $\frac{best_{\text{in verification}} - best_{\text{in paper}}}{best_{\text{in paper}}} \times 100%$.

CPLEX 20.1 verification conclusion

The computational results for the EVRP-TW-SPD dataset in our repository align with those from the dataset officially used in the paper by Akbay et al. (2022), except for the running times in CPLEX (due to different .ops files and running machines), indicating the correctness of the EVRP-TW-SPD dataset generation.

References

  • Akbay, M. A., Kalayci, C. B., & Blum, C. (2022). Application of cmsa to the electric vehicle routing problem with time windows, simultaneous pickup and deliveries, and partial vehicle charging. In Metaheuristics International Conference (pp. 1-16). Cham: Springer International Publishing.
  • Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation science, 48(4), 500-520.
  • Salhi, S., & Nagy, G. (1999). A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. Journal of the operational Research Society, 50, 1034-1042.