Highlights 4 mathematical cases for maximum benefit multi-vehicle arc routing are presented. Benefits of relaxing assumptions of k-CPP such as closed loop routes are discussed. The usefulness of each case is described. The performance of three of the cases are compared and illustrated.
Abstract 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.
Generalized Maximum Benefit Multiple Chinese Postman Problem
Tramsportation Research, Part C: Emerging Technologies ; 55 ; 261-272
2015-01-22
12 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Generalized Maximum Benefit Multiple Chinese Postman Problem
Online Contents | 2015
|Public sector vehicle routing : the Chinese-postman problem
TIBKAT | 1970
|The Chinese Postman Problem with Load-Dependent Costs
British Library Online Contents | 2018
|