Solving Transport Problems

4A Ruin and Recreate Solution Method for a Lexicographic Vehicle Routing Problem Integrating Park-and-Loop and Car Sharing

The vehicle routing problem (VRP) aims at finding optimal vehicle routes that visit a set of jobs in a given region. In the classical VRP formulation, each employee moves from a job to another by driving her/his assigned car. In the proposed generalization of the VRP, workers are allowed to walk or use a light transportation mode, and car sharing is additionally enabled, as a heavy resource can transport more than one worker. These new features are likely to reduce both the driving distance and the heavy-vehicle fleet, which are the two main objective functions optimized in the VRP literature, where, in general, minimizing the number of used vehicles is the primary objective. Such gains on the distance traveled by heavy transportation resources, as well as on the number of heavy vehicles used, have a direct and positive influence on the environmental impact of the undertaken transportation activities.

4.1. Introduction

The Vehicle Routing Problem (VRP) aims at finding optimal vehicle routes that visit a set of jobs in a given region. Depending on the situation, a job can be a service provided on-site, a delivery of goods, or a collection of components. For each job, we know its duration as well as its time window during which it must be performed. When building the routes of the workers for performing the on-site services, the systematic use of cars (which ...