This repository addresses the problem of safe and energy-efficient routing of last-mile electric freight vehicles. With the rising environmental footprint of the transportation sector and the growing popularity of E-Commerce, freight companies are likely to benefit from optimal time-window-feasible tours that minimize energy usage while reducing traffic conflicts at intersections and thereby improving safety. This problem is formulated as a Bi-criterion Steiner Traveling Salesman Problem with Time-Windows (BSTSPTW) with energy consumed and the number of left turns at intersections as the two objectives while also considering regenerative braking capabilities. We first discuss an exact mixed-integer programming model with scalarization to enumerate points on the efficiency frontier for small instances. For larger networks, an efficient local search-based heuristic is developed. This heuristic uses several operators to intensify and diversify the search process. The utility of the proposed methods is demonstrated using a benchmark data set and real-world data from Amazon delivery routes in Austin, US. The results show that the proposed heuristics can generate near-optimal solutions within reasonable time budgets, striking a balance between energy efficiency and safety under practical delivery constraints.
- Before running the code, install the required packages using the following command:
pip install -r requirements.txt- Requires Python>= 3.9.8.
- Operating System: Ubuntu 20.04.3 LTS.
- Requires CPLEX (Full Version) for running the MIP model.
- Download the sample instances from the following (Link) and place them in the main directory.
- For running MIP model on benchmark instances, ensure the test instances are in folder "milpInputs". Run the following command:
python mainIP.py - For running local search on Amazon dataset, ensure the routes have been processed and saved in folder "./lsInputs/". A test instance (route Id 4946) has been provided. Run the following command:
python mainLS.py - For operator analysis, run the following command:
python mainOperatorAnalysis.py - For running a different instance, run
python preprocessing.py
We welcome all suggestions from the community. If you wish to contribute or report any bug please contact the creaters or create an issue on issue tracking system.
-
Prateek Agarwal
- Ph.D. at Indian Institute of Science (IISc) Bengaluru, India.
- Mail Id: [email protected]
- https://sites.google.com/view/prateek-agarwal/
-
Debojjal Bagchi
- Ph.D. at The University of Texas at Austin.
- Mail Id: [email protected]
- https://debojjalb.github.io/
The content of this repository is bounded by MIT License. For more information see COPYING file
We would like to extend our gratitude to our co-authors, Dr. Tarun Rambha ([email protected]) and Dr. Venktesh Pandey ([email protected]) for their invaluable support and guidance throughout the project. We also thank Dr. Vivek Vasudeva ([email protected]) for reviewing the code.