A Simulated Annealing Heuristic for the Capacitated Green Vehicle Routing Problem

Abstract EN

This research studies the capacitated green vehicle routing problem (CGVRP), which is an extension of the green vehicle routing problem (GVRP), characterized by the purpose of harmonizing environmental and economic costs by implementing effective routes to meet any environmental concerns while fulfilling customer demand.

We formulate the mathematical model of the CGVRP and propose a simulated annealing (SA) heuristic for its solution in which the CGVRP is set up as a mixed integer linear program (MILP).

The objective of the CGVRP is to minimize the total distance traveled by an alternative fuel vehicle (AFV).

This research conducts a numerical experiment and sensitivity analysis.

The results of the numerical experiment show that the SA algorithm is capable of obtaining good CGVRP solutions within a reasonable amount of time, and the sensitivity analysis demonstrates that the total distance is dependent on the number of customers and the vehicle driving range.