Incorporating linear optimization into routing problems

Research output: Contribution to conferenceAbstractAcademic


This work introduces a heuristic algorithm for the Vehicle Routing Problem with Time Windows (VRPTW) that greedily constructs a routing plan by employing a master Linear Programming (LP) model as a central optimization mechanism. The objects to select in the LP model are routes that are bi-directionally constructed by a Dynamic Programming (DP) based method. Different from classical depot-to-depot type route construction in the literature, our routes are initialized at certain customers, so called route centers, and they are extended by visiting further customers before and after already visited ones. Here, a route center corresponds to a used vehicles, and a clique in the customer incompatibility graph gives us initial route centers. A complete routing plan, i.e. an integer solution to the master LP model, is obtained by making two type of decisions; customer grouping and introducing a new vehicle. These decisions are made by examining solution properties of the dual our master LP model. We also give a dual interpretation of the master LP model by using the primal-dual method as a base for our decision system. An important feature of our algorithm is that every used vehicle has a fixed-size route set in the master LP model which makes our algorithm to halt in constant time. The efficiency of our algorithm is shown by means of a computational study by using well-known Solomon VRPTW benchmark instances.
Original languageEnglish
Publication statusPublished - 2017
Event28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland - Poznan Univeristy of Technology , Poznan, Poland
Duration: 3 Jul 20166 Jul 2016


Conference28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland
Abbreviated titleEURO 2016
Internet address


Dive into the research topics of 'Incorporating linear optimization into routing problems'. Together they form a unique fingerprint.

Cite this