The multi-depot open location routing problem with a heterogeneous fixed fleet

Abstract

This paper introduces the multi-depot open location routing problem (MD-OLRP) with a heterogeneous fixed fleet. The problem is inspired by the collection problem of a company which collects raw materials from different suppliers coordinating several carriers. Each carrier has a heterogeneous fixed fleet. Moreover, there is a fixed cost for contracting each vehicle and a variable cost associated with the distance traveled. The empty haul return to the vehicles depot is not considered in the cost. The raw materials collected are delivered to a single delivery point. The problem is modeled as a Mixed Integer Linear Program (MILP) that minimizes the total cost, selecting the carriers to be contracted, the vehicles to be used from each contracted carrier and the collection routes. For small instances, the model can be solved to optimality. However, approximate procedures are necessary to handle larger instances. In this sense, in the present work we propose an intelligent metaheuristic which incorporates problem specific knowledge to solve it. The computational results show that the solution method is computationally efficient and provides high quality solutions. In particular, the new solution obtained for the case of study generates savings of 30.86% to the company. The main contributions of the paper are the new problem statement that was not found in the literature, its association to the real problem of a company and the intelligent metaheuristic proposed to solve it. Additional experimentation used the model proposed to solve a simpler problem obtaining new best solutions compared to those reported in the recent literature