Scientific Program > Talks by Speaker > Santos Daniel

Multi-depot routing problems arise in distribution logistics where a set of vehicles based at several depots are used to serve a number of clients. Most variants of this problem have the basic requirement that the route of each vehicle starts and ends at the same depot. This paper describes new inequalities, namely multi-cut constraints (MCC), for multi-depot routing problems that enforce this requirement. The MCCs are exponential in size, and are equivalent to a compact three-index formulation for the problem in terms of the associated linear programming relaxations. The paper describes how a generalization of the MCCs can be obtained, in a similar manner, by using a stronger version of the three-index formulation. The connection between the compact and the exponential formulations implies a separation procedure based on max-flow/min-cut computations, which has reduced complexity in comparison with a previously known set of constraints described for the same purpose. The new inequalities are used in a branch-and-cut algorithm. Computational results with instances with 100 clients and up to 10 depots indicate that the algorithm is able to optimally solve the instances generally within a few hundred seconds of computation time.