Multivehicle routing with profits and competition

Download the paper, pdf.


E. Thorson
University Transportation Research Center
Marshak Science Building, J-910
City College of New York
New York, NY 10031
ethor at

J. Holguín-Veras
Department of Civil and Environmental Engineering
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
jhv at

J. E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at

Citation details:

October 2005.


This paper deals with a multiple vehicle routing problem in which profit is maximized subject to competition. This problem will be referred to as the multiple vehicle routing problem with profits and competition (MVRPPC). The MVRPPC differs from traditional multivehicle routing problems in three ways: (1) competition is incorporated into the process, (2) the objective is to maximize profits rather than minimize costs, and (3) it is assumed that trucks leave and return to their home bases empty, thus any freight picked up in a tour must be delivered in that same tour (which represents the case of for-hire carriers). The solution method takes a cluster first, route second approach in which the clustering phase combines a geometric clustering with a generalized assignment problem (GAP). The routing is performed using a tabu search. To get an idea of how well the tabu search performs, an alternative method for routing was developed which consisted of a mixed integer program (MIP) based on the flow formulation of the traveling salesman problem. The solution approach was applied to a series of problems of varying size and complexity with the routing performed by both the tabu search and the MIP formulations. A comparison of the tabu search and MIP solutions indicated that the tabu search solutions were practically the same than the corresponding MIP solutions, with tabu search objective function values which were no more than 0.70% of the MIP values. As an illustration of the potential uses of the methodologies developed, the paper analyzes the role of the degree of market transparency on the geographic segmentation of the market.

Download the paper, pdf.

Return to my list of papers.