The Round-Trip p -Center and Covering Problem on a Tree

Antoon Kolen
Additional contact information
Antoon Kolen: Erasmus University, Rotterdam, The Netherlands

Transportation Science, 1985, vol. 19, issue 3, 222-234

Abstract: A task performed by a vehicle consists of picking up goods at a given client and delivering it to another client. The round-trip distance is the distance traveled by the vehicle between the departure from and the return to its depot. The round-trip p-center problem is to locate p depots with respect to a finite number of pairs of clients so as to minimize the maximum round-trip cost, which is defined as a nonlinear increasing function of the round-trip distance from the nearest depot. The round-trip covering problem is to find the minimum number of depots such that each round-trip cost is no more than a given constant. For both problems a dual problem is defined and in case the underlying network is a tree a strong duality result is proved. We give algorithms to solve both tree round-trip location problems in polynomial time.

Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.19.3.222 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:19:y:1985:i:3:p:222-234

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().