Column Generation Based Approaches for Combined Routing and Scheduling

The multi-trip location routing problem is usually applied in the logistics and transportation field. The multi-trip location routing problem is an integrated problem that combines two important and difficult optimization problems: the facility location problem and the multi-trip vehicle routing problem. In the facility location problem, one has to determine the set of facilities that can be used to serve the clients. To fulfill the clients needs, we generate a set of routes by solving a multi-trip vehicle routing problem which allows the assignment of more than one single-trip to a vehicle along the planning horizon. To solve the multi-trip location routing problem, we propose a column generation approach that integrates these two problems. In practice, both the facility location problem and the multi-trip vehicle routing problem are solved simultaneously. This approach leads to better solutions than those achieved by solving the two problems separately. Computational results are described at the end of the paper to illustrate the potential of this approach.