Geoscience Reference
In-Depth Information
districts are needed to define for each inhabitant which facility he should visit to
obtain service, for example for preventive medical examinations, or to determine
areas of responsibility of home-care visits by healthcare personnel, like nurses or
physiotherapists. The goal is to determine contiguous districts that have a good
accessability with respect to public transportation and have an equitable workload
based on service and travel time or account for a high capacity utilization of the
social facility (cf. Minciardi et al.
1981
; Blais et al.
2003
; Benzarti et al.
2013
).
A second field of applications deals with providing service to streets. A classical
problem concerns the design of districts for postal or leaflet delivery. Instead of
considering each household separately, districts are composed of whole streets.
Thus, basic units correspond to streets and each basic unit typically has two
attributes: the times required to traverse the street with and without providing
service. The task is to partition the streets into a given number of districts such
that the required delivery time is approximately the same for all districts and
does not exceed the working time restriction of the deliverer. The delivery time is
proportional to the length of a Chinese postman tour through the district, which can
be computed efficiently. Moreover, the delivery districts should be contiguous, incur
little deadheading, and should not overlap, i.e., be geographically compact (Bodin
and Levy
1991
;Butschetal.
2014
). A common characteristic of these applications is
that the deliverer either walks through his district on foot or goes by bike so that one-
way streets are no hindrance. If a street is toowideorhastoomuchtraffictoserveit
in a zig-zag pattern, then each side of the street is modeled as a separate basic unit. A
similar problem arises in the context of meter reading in power distribution networks
(Silva de Assis et al.
2014
). Closely related are districting problems for solid waste
disposal, salt spreading, and winter gritting (Hanafi et al.
1999
; Muyldermans et al.
2002
; Lin and Kao
2008
). The criteria are almost identical to postal delivery. The
only differences are that vehicles typically have to respect one-way streets and have
difficulties making U-turns, and that their tours have to include a depot, e.g., to drop
off waste or refill salt. All these aspects make the computation of the travel times
more difficult. Other applications deal with the design of patrol districts for police
cars and primary response areas for ambulances, where the districts additionally
should have an average response time and/or incident arrival rate below a given
threshold (Baker et al.
1989
; D'Amico et al.
2002
;XuandYum
2010
).
Other applications deal with the problem of assigning residential areas to schools
(Ferland and Guénette
1990
; Schoepfle and Church
1991
). Criteria to be taken
into account are capacity limitations and an equal utilization of the schools,
maximal or average travel distances for students, good accessability, and ethnic
balance. Another aspect is to decide which students should walk to school and
which should take the school bus. Districting problems also occur in electric
power networks. According to Bergey et al. (
2003
), the World Bank regularly
faces the challenge of helping developing countries to move from state owned,
monopolistic electric utilities to a more competitive environment with multiple
electricity service providers. At that, they face the task of partitioning the physical
power grid into economically viable districts (distribution companies). The main
aim is to determine non-overlapping and contiguous districts with approximately
