A continuous districting model focusing on intra‐ and inter‐zonal squared distances and its Voronoi‐based heuristic

• Author: Ken‐ichi Tanaka,Keitaro Morimoto
• Date: 01 May 2021
• Published date: 01 May 2021
• DOI: http://doi.org/10.1111/itor.12893

Intl. Trans. in Op. Res. 28 (2021) 1109–1134

DOI: 10.1111/itor.12893

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A continuous districting model focusing on intra- and

inter-zonal squared distances and its Voronoi-based heuristic

Keitaro Morimotoaand Ken-ichi Tanakab,∗

aGraduate School of Science and Technology, Keio University, 3-14-1 Hiyoshi, Kohoku-ku,Yokohama,

Kanagawa 223-8522, Japan

bFaculty of Science and Technology, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama, Kanagawa223-8522, Japan

E-mail: keitaro_morimoto_222@keio.jp[Morimoto]; ken1tnk@ae.keio.ac.jp [Tanaka]

Received 31 January 2020; received in revised form 9 September 2020; accepted 5 October 2020

Abstract

We consider the problem of dividing a given convex polygon into pconvex polygons called zones, each of

which receives a designated land area. The position and shape of each zone is determined so that intra- and

inter-zonal trips for the resulting zones are conducted efficiently. To evaluatethe compactness of the resulting

zones, we derive the average squared distance between two points uniformly distributed in each zone, as well

as the average squared distance between two points uniformly distributed in two zones. The weighted sum of

these measures is used as the objective function, and a Voronoi-based heuristic algorithm is proposed that

iteratively updates the positions of pgenerator points placed inside a convex polygon. The method is used to

divide several regular polygons, and the results show that zones become (i) rounded when intra-zonal trips

are prioritized and (ii) elongated with longer boundary lines when inter-zonal trips are prioritized.

Keywords:continuous districting problem; intra- and inter-zonal trips; squared distance; Voronoitessellation

1. Introduction

We consider the following continuous districting problem. Given a convex region Rwith area s,we

aim to divide Rinto pconvex subregions Z1,...,Zpcalled zones, each of which must be allocated

a prespecified area s1,...,sp, respectively. We focus on two types of trips in the resulting division,

namely, (i) intra-zonal trips that originate and terminate in the same zone and (ii) inter-zonal trips

that take place between two different zones. The objective is to determine the positions and shapes

of the zones so that trips within and between them can be conducted efficiently.

As an application of this model, let us focus on designing a university campus consisting of p

different departments in a given area Rso that each department is allocated a given land area.

∗Corresponding author.

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1110 K. Morimoto and K. Tanaka / Intl. Trans. in Op. Res. 28 (2021) 1109–1134

Fig. 1. Division of a convex polygon into zones with intra-zonal (solid lines) and inter-zonal trips (dashed lines).

Among (infinitely) many plans that satisfy the area constraint, a desirable division is one in which

(i) trips within the same department can be conducted easily and (ii) two departments with a high

frequency of trips between them are positioned close to each other.The proposed framework would

also be useful when designing pzones in a given land area, such as designing plants, factories,

offices, and many other facilities.

We briefly introduce the proposed model. As a measure to describe the compactness of each

zone Zi(intra-zonal trips), we use the average squared distance r2

ibetween two points uniformly

distributed in each zone. Also, we measure the degree of connection between zones Ziand Zjby

the average squared distance d2

ijbetween two points uniformly distributed in the respective zones.

This simplifying assumption has been extensively used in existing continuous transportation and

districting models (e.g., Vaughan, 1984; Suzuki & Drezner, 2009; Carlsson & Devulapalli, 2013). It

facilitates an analytical approach to the problem and allows exact formulas to be obtained for r2

i

and d2

ij. Note that in reality, the frequency of trips depends on the trip length and thus the division

of the region. It is expected that this distance-decay structure is not so influential when the target

area is not very large. In such situations, the model holds important implications for real-world

districting problems. The proposed model is formulated as follows:

minimize

p



i=1

αir2

i+

p−1



i=1

p



j=i+1

βijd2

ij,(1)

subject to si=ais,i=1,...,p.(2)

Here, αiis the weight given to the trip within zone Zi,andβij is the weight given to the trip between

zones Ziand Zj. The values of βij should be set based on the importance of each trip pattern.

ai∈(0,1) is the ratio of the area of zone Zito the total area of s. Objective function (1) is the

weighted sum of paverage squared intra-zonal distances and p(p−1)/2 average squared inter-

zonal distances. By minimizing this function, we expect to obtain a desirable division in terms of

compactness in each polygon and good connection between any two polygons.

As shown in Fig. 1, we deal with the situation in which the resultant zones are convex polygons,

which delivers analytical and algorithmic advantages. First, the average squared distances within

and between zones, namely, r2

iand d2

ij, can be obtained analytically in the case of polygonal

zones. Second, we can use a Voronoi-based approach to solve the proposed problem. Because it

would be difficult to find a globally optimal solution forthis problem, we propose instead a heuristic

algorithm to find a desirable approximate solution. To divide Rinto convex polygons, we use the

© 2020 The Authors.

International Transactionsin Operational Research © 2020 International Federation of OperationalResearch Societies