A 2-COMMODITY FLOW FORMULATION FOR THE TRAVELING SALESMAN AND THE MAKESPAN PROBLEMS WITH TIME WINDOWS

Authors
LANGEVIN A DESROCHERS M DESROSIERS J GELINAS S SOUMIS F
Citation
A. Langevin et al., A 2-COMMODITY FLOW FORMULATION FOR THE TRAVELING SALESMAN AND THE MAKESPAN PROBLEMS WITH TIME WINDOWS, Networks, 23(7), 1993, pp. 631-640
Citations number
16
Categorie Soggetti
Mathematics,"Computer Sciences","Computer Applications & Cybernetics
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
23
Issue
7
Year of publication
1993
Pages
631 - 640
Database
ISI
SICI code
0028-3045(1993)23:7<631:A2FFFT>2.0.ZU;2-G
Abstract
We present a new two-commodity flow formulation for the traveling sale sman problem. Each commodity corresponds to a resource that is either distributed or picked up along the tour of all nodes. This formulation is partcularly well suited to handling time window constraints; the r esource used is then the time. This formulation can be extended to the makespan problem. For a n-node problem, the linear relaxation of the formulation involves only O(n) constraints and O(n2)variables. Impleme ntation issues are discussed and numerical experimentations have been realized for problems of up to 60 nodes. (C) 1993 by John Wiley & Sons , Inc.