Groupe d’études et de recherche en analyse des décisions

G-88-22

Optimisation de l'horaire d'initinéraire, avec coûts convexes

, et

We present an algorithm that solve the problem of finding the best vehicle time schedule (minimizing total inconveniences) for a fixed path, knowing that visiting times are constrained by time windows and that inconveniences are modelized as convex functions of visiting time. This problem occurs in the last step or as a sub-problem in Benders' decomposition, in many approachs used to solve routing and scheduling problems. We show that the algorithm complexity is linear in number of unidimentional minimizations for the convex case and is linear in number of operations for the quadratic and linear cases of the inconvenience functions. Extensions with linear cost on waiting times, and discret times are presented.

, 23 pages