DEPTH-FIRST SOLUTIONS FOR THE DELIVERYMAN PROBLEM ON TREE-LIKE NETWORKS: AN EVALUATION USING A PERMUTATION MODEL

The Deliveryman Problem, or DMP (also referred to as the Traveling Repairman Problem TRP), requires a single traveling service unit with a specified home location to serve a set of customers, each of which has a weight or priority. The objective is to find a tour which minimizes a weighted average of the times the customers wait for service. This paper examines the effectiveness of depth-first routes for the DMP on tree and cactus networks. Depth-first routes involve traversing the tree or cactus network in depth-first manner. The best depth-first solution for the DMP can be found very quickly. The evaluation of depth-first routes on general tree and cactus networks is based on a novel formulation for the DMP which employs permutation decision variables and includes as constraints necessary optimality conditions based on network structure.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/1767714
• Corporate Authors:

  Institute for Operations Research and the Management Sciences (INFORMS)

  901 Elkridge Landing Road, Suite 400
  Linthicum, MD  United States  21090-2909
• Authors:
  • Webb, I R
• Publication Date: 1996-5

Language

• English

Media Info

• Features: Figures; References; Tables;
• Pagination: p. 134-147
• Serial:
  • Transportation Science
  • Volume: 30
  • Issue Number: 2
  • Publisher: Institute for Operations Research and the Management Sciences (INFORMS)
  • ISSN: 0041-1655
  • Serial URL: http://transci.journal.informs.org/

Subject/Index Terms

• TRT Terms: Customers; Delivery service; Traveling salesman problem; Trees (Mathematics); Waiting time
• Subject Areas: Highways; Planning and Forecasting; I10: Economics and Administration;

Filing Info

• Accession Number: 00721942
• Record Type: Publication
• Files: TRIS
• Created Date: Jun 26 1996 12:00AM