On the Routing and Location of Mobile Facilities

dc.contributor.advisorRaghavan, Subramanianen_US
dc.contributor.authorHalper, Russell Daviden_US
dc.contributor.departmentApplied Mathematics and Scientific Computationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2010-07-02T05:43:56Z
dc.date.available2010-07-02T05:43:56Z
dc.date.issued2010en_US
dc.description.abstractMobile facilities play important roles in many applications, including health care, public services, telecommunications, and humanitarian relief logistics. While mobile facilities operate in different manners, it is generally considered important for a decision maker to be capable of efficiently deploying mobile facilities. This dissertation discusses two problems on the use of mathematical models and algorithms for determining efficient deployments of mobile facilities. First we discuss the mobile facility routing problem (MFRP), which effectively models the operations of a wide class of mobile facilities that have significant relocation times and cannot service demand during transit. Chapter 2 discusses the single MFRP (SMFRP), which is to determine a route for a single mobile facility to maximize the demand serviced during a continuous-time planning horizon. We present two exact algorithms, and supporting theoretical results, when the rate demand is generated is modeled using piecewise constant functions. The first is a dynamic program that easily extends to solve cases where the demand functions take on more general forms. The second exact algorithm has a polynomial worst-case runtime. Chapter 3 discusses the MFRP, which addresses the situation when multiple mobile facilities are operating in an area. In such a case, mobile facilities at different locations may provide service to a single event, necessitating the separation of the events generating demand from the locations mobile facilities may visit in our model. We show that the MFRP is NP-hard, present several heuristics for generating effective routes, and extensively test these heuristics on a variety of simulated data sets. Chapter 4 discusses formulations and local search heuristics for the (minisum) mobile facility location problem (MFLP). This problem is to relocate a set of existing facilities and assign clients to these facilities while minimizing the movement costs of facilities and clients. We show that in a certain sense the MFLP generalizes the uncapacitated facility location and p-median problems. We observe that given a set of facility destinations, the MFLP decomposes into two polynomially solvable subproblems. Using this decomposition observation, we propose a new, compact IP formulation and novel local search heuristics. We report results from extensive computational experiments.en_US
dc.identifier.urihttp://hdl.handle.net/1903/10273
dc.subject.pqcontrolledApplied Mathematicsen_US
dc.subject.pqcontrolledOperations Researchen_US
dc.subject.pqcontrolledMathematicsen_US
dc.subject.pquncontrolledFacility Locationen_US
dc.subject.pquncontrolledMFLPen_US
dc.subject.pquncontrolledMFRPen_US
dc.subject.pquncontrolledMobile Facilityen_US
dc.subject.pquncontrolledMobile Facility Location Problemen_US
dc.subject.pquncontrolledMobile Facility Routing Problemen_US
dc.titleOn the Routing and Location of Mobile Facilitiesen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Halper_umd_0117E_11102.pdf
Size:
854.24 KB
Format:
Adobe Portable Document Format