Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm

Hongtao Lei; Rui Wang; Gilbert Laporte

doi:10.1016/j.cor.2015.09.002

Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm

Hongtao Lei, Rui Wang, Gilbert Laporte

Research output: Contribution to journal › Article › peer-review

62 Citations (SciVal)

Abstract

This study considers a multi-objective dynamic stochastic districting and routing problem in which the customers of a territory stochastically evolve over several periods of a planning horizon, and where the number of service vehicles, the compactness of the districts, the dissimilarity measure of the districts and an equity measure of vehicles profit are considered as objectives. The problem is modeled and solved as a two-stage stochastic program, where in each period, districting decisions are made in the first stage, and the Beardwood-Halton-Hammersley formula is used to approximate the expected routing cost of each district in the second stage. An enhanced multi-objective evolutionary algorithm (MOEA), i.e., the preference-inspired co-evolutionary algorithm using mating restriction, is developed for the problem. The algorithm is tested on randomly generated instances and is compared with two state-of-the-art MOEAs. Computational results confirm the superiority and effectiveness of the proposed algorithm. Moreover, a procedure for selecting a preferred design for the proposed problem is described.

Original language	English
Pages (from-to)	12-24
Number of pages	13
Journal	Computers and Operations Research
Volume	67
DOIs	https://doi.org/10.1016/j.cor.2015.09.002
Publication status	Published - 1 Mar 2016

Funding

This work was partly supported by the Chinese National Natural Science Foundation under grants 71201170 and 61403404 , and by the Hunan Provincial Natural Science Foundation of China under grant 13JJ4010 , by the Specialized Research Fund for the Doctoral Program of Higher Education of China under grant 20124307120024 , by the Research Plan of National University of Defense Technology under grant JC14-05-01 , and by the Canadian Natural Sciences and Engineering Research Council under grant 39682-10 . This support is gratefully acknowledged. Thanks are due to the referees for their valuable comments.

Keywords

Co-evolutionary algorithm
Districting
Mating restriction
Multi-objective optimization
Routing

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research

Access to Document

10.1016/j.cor.2015.09.002

Cite this

@article{c37c34e342a24491931d9725188e866d,

title = "Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm",

abstract = "This study considers a multi-objective dynamic stochastic districting and routing problem in which the customers of a territory stochastically evolve over several periods of a planning horizon, and where the number of service vehicles, the compactness of the districts, the dissimilarity measure of the districts and an equity measure of vehicles profit are considered as objectives. The problem is modeled and solved as a two-stage stochastic program, where in each period, districting decisions are made in the first stage, and the Beardwood-Halton-Hammersley formula is used to approximate the expected routing cost of each district in the second stage. An enhanced multi-objective evolutionary algorithm (MOEA), i.e., the preference-inspired co-evolutionary algorithm using mating restriction, is developed for the problem. The algorithm is tested on randomly generated instances and is compared with two state-of-the-art MOEAs. Computational results confirm the superiority and effectiveness of the proposed algorithm. Moreover, a procedure for selecting a preferred design for the proposed problem is described.",

keywords = "Co-evolutionary algorithm, Districting, Mating restriction, Multi-objective optimization, Routing",

author = "Hongtao Lei and Rui Wang and Gilbert Laporte",

year = "2016",

month = mar,

day = "1",

doi = "10.1016/j.cor.2015.09.002",

language = "English",

volume = "67",

pages = "12--24",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

}

TY - JOUR

T1 - Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm

AU - Lei, Hongtao

AU - Wang, Rui

AU - Laporte, Gilbert

PY - 2016/3/1

Y1 - 2016/3/1

N2 - This study considers a multi-objective dynamic stochastic districting and routing problem in which the customers of a territory stochastically evolve over several periods of a planning horizon, and where the number of service vehicles, the compactness of the districts, the dissimilarity measure of the districts and an equity measure of vehicles profit are considered as objectives. The problem is modeled and solved as a two-stage stochastic program, where in each period, districting decisions are made in the first stage, and the Beardwood-Halton-Hammersley formula is used to approximate the expected routing cost of each district in the second stage. An enhanced multi-objective evolutionary algorithm (MOEA), i.e., the preference-inspired co-evolutionary algorithm using mating restriction, is developed for the problem. The algorithm is tested on randomly generated instances and is compared with two state-of-the-art MOEAs. Computational results confirm the superiority and effectiveness of the proposed algorithm. Moreover, a procedure for selecting a preferred design for the proposed problem is described.

AB - This study considers a multi-objective dynamic stochastic districting and routing problem in which the customers of a territory stochastically evolve over several periods of a planning horizon, and where the number of service vehicles, the compactness of the districts, the dissimilarity measure of the districts and an equity measure of vehicles profit are considered as objectives. The problem is modeled and solved as a two-stage stochastic program, where in each period, districting decisions are made in the first stage, and the Beardwood-Halton-Hammersley formula is used to approximate the expected routing cost of each district in the second stage. An enhanced multi-objective evolutionary algorithm (MOEA), i.e., the preference-inspired co-evolutionary algorithm using mating restriction, is developed for the problem. The algorithm is tested on randomly generated instances and is compared with two state-of-the-art MOEAs. Computational results confirm the superiority and effectiveness of the proposed algorithm. Moreover, a procedure for selecting a preferred design for the proposed problem is described.

KW - Co-evolutionary algorithm

KW - Districting

KW - Mating restriction

KW - Multi-objective optimization

KW - Routing

UR - http://www.scopus.com/inward/record.url?scp=84944080692&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2015.09.002

DO - 10.1016/j.cor.2015.09.002

M3 - Article

AN - SCOPUS:84944080692

SN - 0305-0548

VL - 67

SP - 12

EP - 24

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

Solving a multi-objective dynamic stochastic districting and routing problem with a co-evolutionary algorithm

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this