Back to search

University of the Aegean

Solving the dynamic vehicle routing problem with mixed backhauls through re-optimization

Abstract

dc:description

In this dissertation we studied the Dynamic Vehicle Routing Problem with Mixed Backhauls (DVRPMB), which seeks to assign, in the most efficient way, dynamic pick-up requests that arrive in real-time while a predefined distribution plan is being executed. We used periodic re-optimization to deal with the dynamic arrival of pick-up orders. We developed the formulation of the re-optimization problem, and re-modelled it to a form amenable to applying Branch-and-Price (B&P) for obtaining exact solutions. In order to address challenging cases (e.g. without time windows), we also proposed a novel Column Generation-based insertion heuristic that provides near-optimal solutions in an efficient manner.Using the aforementioned approach, the dissertation focused on the re-optimization process for addressing the DVRPMB, which comprises a) the re-optimization policy, i.e. when to re-plan, and b) the implementation tactic, i.e. what part of the new plan to communicate to the fleet drivers. We presented and analyzed several re-optimization strategies (combinations of policy and tactic) often met in practice by conducting an extensive series of designed experiments. We did so, by assuming initially unlimited fleet resources under a straightforward objective (i.e. minimize distance traveled). Based on the results obtained, we proposed guidelines for the selection of the appropriate re-optimization strategy with respect to various key problem characteristics (geographical distribution, time windows, degree of dynamism, etc.).Subsequently, we In this dissertation we studied the Dynamic Vehicle Routing Problem with Mixed Backhauls (DVRPMB), which seeks to assign, in the most efficient way, dynamic pick-up requests that arrive in real-time while a predefined distribution plan is being executed. We used periodic re-optimization to deal with the dynamic arrival of pick-up orders. We developed the formulation of the re-optimization problem, and re-modelled it to a form amenable to applying Branch-and-Price (B&P) for obtaining exact solutions. In order to address challenging cases (e.g. without time windows), we also proposed a novel Column Generation-based insertion heuristic that provides near-optimal solutions in an efficient manner.Using the aforementioned approach, the dissertation focused on the re-optimization process for addressing the DVRPMB, which comprises a) the re-optimization policy, i.e. when to re-plan, and b) the implementation tactic, i.e. what part of the new plan to communicate to the fleet drivers. We presented and analyzed several re-optimization strategies (combinations of policy and tactic) often met in practice by conducting an extensive series of designed experiments. We did so, by assuming initially unlimited fleet resources under a straightforward objective (i.e. minimize distance traveled). Based on the results obtained, we proposed guidelines for the selection of the appropriate re-optimization strategy with respect to various key problem characteristics (geographical distribution, time windows, degree of dynamism, etc.).Subsequently, we studied the case in which the number of available vehicles is limited and, consequently, not all orders may be served. To address this, we proposed the required modifications in both the DVRPMB model and the solution approach. By using a conventional objective that strictly maximizes service, we illustrated through appropriate experimentation that the performance of the re-optimization strategies have similar behavior as in the unlimited fleet case. Furthermore, we proposed novel objective functions that account for vehicle productivity during each re-optimization cycle and we illustrated that these objectives may offer improved customer service, especially for cases with relatively high vehicle availability and wide time windows. Moreover, we applied the proposed method to a case study of a next-day courier service provider and illustrated that the method significantly outperforms both current planning practices, as well as a sophisticated insertion-based heuristic. Finally, we investigated an interesting and novel variant of DVRPMB that allows transfer of delivery orders between vehicles during plan implementation, in order to better utilize fleet capacity and re-distribute its workload as needed in a real-time fashion. We introduced a novel mathematical formulation for the re-optimization problem with load transfers, and proposed an appropriate heuristic that is able to address cases of practical size. We illustrated through extensive experimentation under various operating scenarios that this approach offers significant savings beyond those offered by the previous approaches that do not allow order transfers. χ

Degree

thesis:*
Grantor dc:publisher
University of the Aegean
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Ninikas, Georgios
  • Νινίκας, Γεώργιος

Subjects

dc:subject × 4

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/38966

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Ninikas, Georgios; Νινίκας, Γεώργιος. Solving the dynamic vehicle routing problem with mixed backhauls through re-optimization. University of the Aegean, 2014. http://hdl.handle.net/10442/hedi/38966