Generalized Maximum Benefit Multiple Chinese Postman Problem

Ali Shafahi

doi:10.1016/j.trc.2015.01.017

Return

Generalized Maximum Benefit Multiple Chinese Postman Problem

2015-06-01

PRE

Ali Shafahi *

Ali Haghani

DOI：10.1016/j.trc.2015.01.017

Original

Original request for help

Save

Abstract

En 中文

This research is focused on a generalization on the Max Benefit Chinese Postman Problem and the multiple vehicle variant of the Chinese Postman Problem. We call this generalization, the Generalized Maximum Benefit k-Chinese Postman Problem (GB k-CPP). We present a novel Mixed Integer Programming (MIP) formulation for the GB k-CPP. Four different cases of the model are discussed. The first case, performs arc-routing with profits and assumes that the origin and destination for each vehicle is the same for each cycle and is given by the user. The next case relaxes the assumption that the origin and destination for each vehicle should be the same and allows the users to select possible origins/destinations for vehicles. Case three gets the origin for each vehicle as input and produces a solution based on finding the best destination for each vehicle. The last case, that is very general, allows the optimization model to select possibly different locations for vehicle origin and destination, during each cycle. The different cases are applied to a security patrolling case conducted on the network of University of Maryland at College Park campus and the results are compared. (C) 2015 Elsevier Ltd. All rights reserved.

Keywords:

Chinese Postman Problem (CPP)

Arc routing problems with profit

Multiple vehicle routing

Security patrolling

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.