Multivehicle routing with profits and competition
Download the paper,
pdf.
Authors:
E. Thorson
University Transportation Research Center
Marshak Science Building, J-910
City College of New York
New York, NY 10031
ethor at utrc2.org
J.
Holguín-Veras
Department of Civil and
Environmental Engineering
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
jhv at rpi.edu
J. E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at rpi.edu
Citation details:
October 2005.
Abstract
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.