Drones represent a promising complement to delivery logistics. They offer a fundamentally different performance profile than conventional trucks. They have lower operating costs and higher speeds, at the expense of reduced range and capacity. In scenarios where these limitations are manageable, drones can fully replace traditional delivery trucks. However, in most practical applications, these complementary vehicle types should be strategically combined to leverage their respective operational strengths. This thesis mainly proposes exact mathematical optimization methods for routing problems with drones.
[Read more]
This thesis mainly proposes exact mathematical optimization methods for routing problems with drones.
[Read more]
[Read more]
In this work, we study a variant of the Vehicle Routing Problem with Time Windows (VRPTW), which integrates two operationally relevant features: flexible departure times from the depot and strict limits on route duration. The resulting problem, termed VRPTW with Route Duration Constraint (VRPTWDC), introduces a scheduling dimension that makes the routing computationally challenging and largely unexplored in the literature. We develop an exact branch-cut-and-price algorithm, having as its main feature a bi-bidirectional labeling algorithm for solving the complex pricing subproblem. Indeed, as the only previously proposed efficient labeling algorithm for the VRPTWDC has a mistake, we provide rigorous proofs of its correctness. Computational experiments on benchmark instances demonstrate the effectiveness of the approach.
[Read more]Nous étudions un problème de découpe avec restes réutilisables et incertitudes sur les demandes. Dans la littérature, une formulation stochastique à deux étapes du problème a était proposé. Nous introduisons une formalisation du problème avec un nombre arbitraire d’étapes. Puis, nous introduisons des méthodes de résolutions exactes axées sur la reformulation du problème en problème de flots dans des graphes ou hypergraphes. Pour les instances du problème avec un grand nombre de scénarios, nous proposons des méthodes de relaxation afin de calculer des bornes inférieures quand la relaxation linéaire ne peux être obtenue. Enfin, nous testons la pertinence de l’approche stochastique à l’aide d’un horizon roulant et en testant différents types d’oracle. Nous comparons nos différentes formulations pour des instances à deux étapes avec les instances de la littérature. Nous comparons également nos bornes inférieures introduites et nous montrons que certaines permettent d’aller plus loin en nombre d’étapes que la relaxation linéaire. Enfin, nous montrons qu’effectuer un horizon roulant avec un oracle à trois étapes permet de faire plus d’économies comparé à un oracle à deux étapes sur les instances de la littérature.
[Read more]
Authors: Sylvain Lichau, Ruslan Sadykov, Julien François, Rémy Dupas
Abstract: In this paper, we propose a new set-partitioning model for the two-echelon vehicle routing problem with drones (2E-VRP-D), where partial routes corresponding to drone movements are enumerated using an efficient dynamic program. To solve the model we [Read more]
Abstract: In this paper, we propose a new set-partitioning model for the two-echelon vehicle routing problem with drones (2E-VRP-D), where partial routes corresponding to drone movements are enumerated using an efficient dynamic program. To solve the model we [Read more]