A firefly algorithm for the environmental prize-collecting vehicle routing problem

摘要

In the present research, a new variant of the Vehicle Routing Problem (VRP), the Environmental Prize-Collecting Vehicle Routing Problem (E-PCVRP), is introduced. The E-PCVRP is a selective routing problem that focuses on the maximization of the aggregated prize values collected from the visited nodes while minimizing the fixed and variable cost of the formed routes. In terms of variable cost, the CO2 emissions of the vehicles performing the routes are considered as a load-distance function. The presented solution approach is based on the Firefly Algorithm (FA). The FA is an optimization algorithm, designed for the solution of continuous problems, while the proposed E-PCVRP, requires a discrete solution approach. Addressing the above discrepancy, the Firefly Algorithm based on Coordinates (FAC) is introduced, which incorporates the proposed "Coordinates Related" (CR) encoding/decoding process in the original FA scheme. The CR is a novel process that allows for algorithms designed for continuous optimization to by employed in the solution of discrete problems, such as the VRP. Specifically, the CR utilizes auxiliary vectors for solution representation, containing the Cartesian coordinates of each node, that allows for the original movement equation of the FA to be applied directly. The effectiveness of the FAC algorithm is showed over computational experiments and statistical analysis, in comparison to the performance of other bio-inspired algorithms and a mathematical solver.