Scientific Program > Talks by Speaker > Zbib Hani

The No-Split Multi-Compartment Capacitated Arc Routing Problem (MC-CARP) is an extension of the CARP arising in different applications such as waste collection where different waste types exist at each edge and the fleet of vehicle is multi-compartmented. The aim of the MC-CARP is to find a set of least cost routes that service the demand for each waste type at all required edges without exceeding compartment capacities, with the condition that when a vehicle visits an edge it either picks the totality or none of its demands. We propose a heuristic approach to solve the MC-CARP, consisting of a multi-move descent algorithm that combines traditional CARP local search moves with optimal edge orientation choice and ejection chains. The algorithm iteratively chooses at random a set of moves and computes all the savings obtained from the search of the whole move neighborhood. The savings are then plotted on an alternate moves graph where each MC-CARP edge is transformed into a node and an edge is added between every two nodes presenting a positive saving. A shortest path algorithm is subsequently run on that graph to determine the set of multi-moves that bring the largest saving to the current solution. The algorithm has been tested on a large set of instances obtained from real-life waste collection companies across Denmark, varying in sizes between 25 to 11656 nodes and 18 to 8584 required edges, and in the number of waste types on each edge (2 to 4). Preliminary results thus far are promising.