The Cumulative Capacitated Arc Routing Problem
Juan Carlos Rivera  1, *@  , Sergio Andrés Lenis  1@  
1 : Universidad EAFIT  (EAFIT)  -  Website
Carrera 49 No. 7 sur - 50. Medellín -  Colombia
* : Corresponding author

In this paper we propose a new variant of the Capacitated Arc Routing Problem (CARP). The objective function becomes a flow-based function, i.e. energy consumption minimization since it is computed by multiplying the travelled distance by the vehicle load. Kara et al. (2008) argue that the real cost of a vehicle traveling between two nodes depends on several conditions like the vehicle load, fuel consumption per kilometer, fuel price, time spent or distance travelled, depreciation of the tires and the vehicle, maintenance, driver wages, time spent on visiting all customers, total distance travelled, etc. Even though most of those attributes can be represented by a distance measure, others cannot, i.e. load of the vehicle, fuel consumption per kilometer, maintenance, depreciation of the tires and the vehicle. These attributes can be represented by the flow on the corresponding arcs and allow us to tackle problems related to garbage trucks, salt spreaders, school buses, etc. more efficiently. Here a mathematical model and a metaheuristic approach are proposed. The metaheuristic approach is based on the hybridization of three known procedures: GRASP, VND and Set covering model. The mathematical model and the metaheuristic are tested with some benchmark instances from CARP. The results allow to evaluate the performance with the different metaheuristic components and to compare the solutions with the classical objective function and the best found solutions by the mathematical model given a reasonable amount of time.

Kara, Imdat, Kara, Bahar, & Kadri, M. 2008. Cumulative Vehicle Routing Problems. 85–98.

Online user: 1 RSS Feed