Incorporating linear optimization into routing problems

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

Uittreksel

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.

Congres

Congres28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland
Verkorte titelEURO 2016
LandPolen
StadPoznan
Periode3/07/166/07/16
Internet adres

Vingerafdruk

Linear programming
Vehicle routing
Heuristic algorithms
Dynamic programming

Citeer dit

Firat, M., Dellaert, N. P., & Nuijten, W. P. M. (2017). Incorporating linear optimization into routing problems. Abstract van 28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland, Poznan, Polen.
Firat, M. ; Dellaert, N.P. ; Nuijten, W.P.M./ Incorporating linear optimization into routing problems. Abstract van 28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland, Poznan, Polen.
@conference{9791621db4194853b8ebe903b6ac485c,
title = "Incorporating linear optimization into routing problems",
abstract = "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.",
author = "M. Firat and N.P. Dellaert and W.P.M. Nuijten",
year = "2017",
language = "English",
note = "28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland, EURO 2016 ; Conference date: 03-07-2016 Through 06-07-2016",
url = "http://www.euro2016.poznan.pl/",

}

Incorporating linear optimization into routing problems. / Firat, M.; Dellaert, N.P.; Nuijten, W.P.M.

2017. Abstract van 28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland, Poznan, Polen.

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

TY - CONF

T1 - Incorporating linear optimization into routing problems

AU - Firat,M.

AU - Dellaert,N.P.

AU - Nuijten,W.P.M.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

M3 - Abstract

ER -

Firat M, Dellaert NP, Nuijten WPM. Incorporating linear optimization into routing problems. 2017. Abstract van 28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland, Poznan, Polen.