An optimal solution procedure for the multiple tour maximum collection problem using column generation

An optimal solution procedure for the multiple tour maximum collection problem using column generation

0.00 Avg rating0 Votes
Article ID: iaor20001565
Country: United Kingdom
Volume: 26
Issue: 4
Start Page Number: 427
End Page Number: 441
Publication Date: Apr 1999
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: travelling salesman, programming: mathematical
Abstract:

The Multiple Tour Maximum Collection Problem (MTMCP) is closely related to the classical Traveling Salesman and Vehicle Routing Problems. One major difference with the MTMCP is that it is not possible to visit all of the nodes in the graph in the total time allocated on a given set of tours. However, with the MTMCP, a reward is collected from each node that is visited. The objective of the MTMCP is to determine which nodes to visit on m time-constrained tours for which the total reward collected is maximized. It is assumed that each tour begins and ends at a central depot and that each node can be visited no more than one time, on at most one tour. In this paper, an optimal solution procedure is presented for the MTMCP. This procedure is based on a set-partitioning formulation and makes efficient use of both column generation and constraint branching. Numerical results are presented which show that this optimal procedure can be used to solve problems of realistic size in a reasonable amount of time.

Reviews

Required fields are marked *. Your email address will not be published.