A TWO-COMMODITY FLOW FORMULATIN FOR THE TRAVELING SALESMAN AND THE MAKESPAN PROBLEMS WITH TIME WINDOWS

This paper presents a new two-commodity flow formulation for the traveling salesman problem. Each commodity corresponds to a resource that is either distributed or picked-up along the tour of all nodes. This formulation is particularly well-suited to handle time window constraints; the resource used is then the time. This formulation can be extended to the makespan problem. For a n-node proble, the linear relaxation of the formulation involves only O(n) constraints and O(n2) variables. Implementation issuesare discussed and numerical experimentations have been realized for problems of up to 40 nodes. (A)

• Corporate Authors:

  CENTRE DE RECHERCHE SUR LES TRANSPORTS. UNIVERSITE DE MONTREAL

  C.P. 6128, SUCCURSALE A
  MONTREAL, QUEBEC  Canada  H3C 3J7
• Authors:
  • Langevin, A
  • DESROCHERS, M
  • Desrosiers, J
  • Soumis, F
• Publication Date: 1990

Language

• English

Media Info

• Features: References;
• Pagination: 13 p.
• Serial:
  • CENTRE DE RECHERCHE SUR LES TRANSPORTS PUBLICATION
  • Issue Number: 732
  • Publisher: Universite de Montreal

Subject/Index Terms

• TRT Terms: Calculation; Freight transportation; Itinerary; Mathematical models; Methodology; Optimization; Theory; Timetables
• Uncontrolled Terms: Optimum
• ITRD Terms: 6464: Calculation; 741: Goods traffic; 699: Itinerary; 6473: Mathematical model; 9102: Method; 9078: Theory; 1186: Timetable
• Subject Areas: Freight Transportation;

Filing Info

• Accession Number: 00674412
• Record Type: Publication
• Source Agency: Transportation Association of Canada (TAC)
• Files: ITRD
• Created Date: Mar 8 1995 12:00AM