synchronized vehicle routing
We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. The synchronization constraints impose a temporal dependency between vehicles, and it follows that a classical decomposition of the vehicle routing and scheduling problem is not directly applicable. We describe some real world problems where in the literature the temporal constraints are usually remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usefulness. We propose two solution approaches. One is an optimization based heuristic. The second is a branch and price algorithm which performs time window branching, and the number of subproblem calls is kept low by adjustment of the columns service times. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct use of a commercial solver against the proposed heuristic, where the latter approach can find high quality solutions within specific time limits. With the branch and price algorithm, we have solved 44 problems to optimality from the 60 problems used for numerical experiments.
| Departamento de Ingeniería Industrial |
| Facultad de Ciencias Físicas y Matemáticas | Universidad de Chile |
República 701, Santiago, Chile | Teléfono:(562)978-4072 | Fax:(562)978-4011