SFU Operations Research Seminar: Jean François Cordeau

Motivated by an application in the routing of technicians at a French public utility, we introduce a highly efficient heuristic together with a branch-price-and-cut algorithm for the doubly open park-and-loop routing problem. This problem is an extension of the classical vehicle routing problem in which routes may involve a main tour performed by driving a vehicle as well as a set of subtours that are carried out on foot after parking the vehicle. In addition, routes do not start and end at a central depot, but rather at customer locations. We first describe a matheuristic based on a split procedure that generates high quality solutions fast. We present computational experiments on a set of real instances with up to 3,800 customers. We also apply the matheuristic to a related problem called the vehicle routing problem with transportable resources, where the method found new best solutions on 32 out of 40 benchmark instances from the literature. We then present an exact algorithm, based on a set-covering formulation of the problem with columns representing complete routes, which is capable of solving to optimality instances with up to 50 customers.