Horizontal arc routing collaboration: models and algorithms

In this work, we investigate horizontal collaboration, mainly on road transportation, among different companies, carriers and shippers. Background motivations are: a still prevalent way of moving around goods in different parts of the world, an increasing pressure on logistic providers and an higher customer expectations about requested service. Therefore, we examine the existing literature on horizontal collaboration classifying different models and techniques used. An extensive literature review about these problems is given. We study profit, benefit and cost allocation procedures in order to better investigate the impact and the effectiveness of collaboration for the collecting of profits and the cutting of costs. Then, we develop a new profitable arc routing model to address a centralized partial cooperation among multiple carriers. We study two different formulations of this problem taking into account the impact of collaboration on the stand alone carrier profit. In the first one the goal is the maximization of the total profit of the coalition of carriers, independently of the individual profit of each carrier. The second variant includes a lower bound on the individual profit of each carrier. We formulate mixed integer programming models for the two variants of the problem and study their properties and their relations with well-known arc routing problems. We solve them with a branch-and-cut algorithm and quantify the impact of collaboration on a large set of instances. Finally, we develope two metaheuristic solution methods based on a Large Neighborhood Search and a Ruin and Repair heuristic framework. On one hand, we have a Variable Neighborhood Search (VNS), on the other hand, we have an Adaptive Large Neighborhood Search (ALNS). Both metaheuristics perform very well on a large set of instances solving almost all of them within few seconds. Moreover, both find feasible solutions on larger and more realistic instances within few minutes.