CONTROLLING TURN PENALTIES IN ARC ROUTING PROBLEMS

In arc routing problems, it is necessary to determine a least cost traversal of some areas on the edge of a graph. Applications of these problems are encountered in such areas as mail delivery, snow removal, street cleaning, and garbage collection. In some problems, the cost of a route is not only determined by the length of driving time, but also by the types of turns made at intersections; for example, left turns are usually more complex and more costly than right turns. It therefore makes sense to assign a cost to each type of turn and account for it in the model and solution process. Traditionally, turn penalties in arc routing problems are taken into account through a transformation of the problem in to an equivalent node routing problem. This paper presents a more direct approach not resorting to such a transformation. Six strategies using the approach are described and tested, and computational results are compared.

• Corporate Authors:

  Center for Transportation Research

  P.O. Box 6128, Station A
  Montreal H3C 3J7,   Canada 
• Authors:
  • Clossey, J
  • Soriano, P
  • Laporte, G
• Publication Date: 1999

Language

• English

Media Info

• Pagination: 18 p.

Subject/Index Terms

• TRT Terms: Cost control; Intersections; Left turns; Right turns; Routing; Turning traffic
• Subject Areas: Highways; Operations and Traffic Management;

Filing Info

• Accession Number: 00792497
• Record Type: Publication
• Files: TRIS
• Created Date: May 27 2000 12:00AM