Incorporating linear optimization into routing problems

Onderzoeksoutput: Bijdrage aan congresAbstract

Samenvatting

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.
Originele taal-2Engels
StatusGepubliceerd - 2017
Evenement28th European Conference on Operational Research (EURO 2016), July 3-6, 2016, Poznan, Poland - Poznan Univeristy of Technology , Poznan, Polen
Duur: 3 jul 20166 jul 2016
http://www.euro2016.poznan.pl/

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

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.