[Back]

C. Bacher, G. Raidl:
"Cyclic Giant Tour Decoding for the EVRPTW";
Talk: European Conference on Operational Research, Poznan, Polen; 2016-07-03 - 2016-07-06.

The scope of our work is the development of efficient route-first-cluster-second decoders for the Electric Vehicle Routing Problem with Time Windows (EVRPTW).
Such a decoder has to fulfill two purposes:
Splitting a permutation of all customer nodes into several feasible routes and inserting recharging stations into the giant tour.

We contribute the following to the field:
First, a giant tour decoder is provided for the EVRPTW. Second, the presented approach relies on Dynamic Programming (DP) for all steps of the procedure.
In contrast the adapted Split-algorithm of (Montoya et al., 2015) for the related Green Vehicle Routing Problem (G-VRP) recomputes the optimal insertion of recharging stations for each evaluated split.
Further the pervasive use of DP allows us to efficiently treat giant tours as cycles, determining the optimal starting position of the first vehicle automatically while avoiding costly recomputations.
As the decoder is intended for future use in heuristic approaches the DP also facilitates partial (re-)evaluation.
Lastly, as a result of our work, we will provide an open source DP framework for declaratively specifying DPs.
The framework borrows the tree grammar analogy of Algebraic Dynamic Programming (Giegerich et al., 2002) and features separation of search tree traversal and evaluation, dominance conditions, search space constraints, and partial invalidation and recomputation.

http://publik.tuwien.ac.at/files/publik_256156.pdf