A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows

Martin Desrochers, François Soumis

INFOR Information Systems and Operational Research · 1988 · 346 citations · 0 references

Concepts

TL;DR

SPPTW seeks the least‑cost route between a source and sink in a network while respecting node time windows. The study proposes an efficient generalized permanent labelling algorithm to solve SPPTW. The algorithm introduces a generalized bucket concept and a specific label‑handling order, achieving pseudo‑polynomial time complexity. The algorithm solved instances with up to 2,500 nodes and 250,000 arcs.

Abstract

The shortest path problem with time windows (SPPTW) consists of finding the least cost route between a source and a sink in a network G = (N, A) while respecting specified time windows [ai, bi] at each visited node. The duration dij of each arc is restricted to positive values while the cost Cij of each arc (i, j) Є A is unrestricted.This article presents an efficient generalized permanent labelling algorithm to solve this problem. This new algorithm is based on the definition of the concept of a generalized bucket and on a specific order of handling the labels. The algorithm runs in pseudo-polynomial time. Problems with up to 2500 nodes and 250,000 arcs have heen solved.