A Restricted Median Location Model for Stop Location Design in Public Transportation Networks

In: The 3rd ORP3 Meeting, Valencia, Spain. P. 297--310, 2005

Authors

• Dwi Retnani Poetranto

Abstract

We consider the location of stops along the edges of an already existing public transportation network. This can be the location of bus stops along some given routes or railway stations along the tracks in a railway network. The goal is to minimize the total distance between demand points to their closest stops, with respect to the rectangular metric. The problem will be treated as a restricted location problem, where the restriction is given by the fact, that optimal locations have to lie on the transportation network. Using a reduction from the rectangular p-median problem, we show that this problem is NP-hard. However, it is shown that if we want to establish only one stop the problem can be solved in polynomial time. This result is used to develop a heuristic algorithm to solve the general problem where we want to establish more than one stop. Two heuristic strategies are proposed and computational results with randomly generated test problems are presented.

BibTeX

 
@InProceedings{ Poetranto:StopLoc, 
   title = { A Restricted Median Location Model for Stop Location Design in Public Transportation Networks }, 
   author = { Dwi Retnani Poetranto },   
   booktitle = { The 3rd ORP3 Meeting, Valencia, Spain },           
   pages = { 297--310 },   
   year = 2005, 
} 

---

This publication belongs to the project DeNDeMA.