1996 Vehicle Routing Problem with Trailers - a Time-Dependent Multi-Trip Vehicle Routing Problem

A time-dependent multi-trip vehicle routing problem

Maoxiang Lang a, Xuesong Zhou b

a MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology，

Beijing Jiaotong University, P. R. China

mxlang@bjtu.edu.cn

b Department of Civil and Environmental Engineering, University of Utah, USA

zhou@eng.utah.edu

Abstract

This paper addresses a time-dependent multi-trip vehicle routing problem. This problem can be detailed as (a) a set of customers with fixed demands and service time windows have to be served in a sequence of service trips which originate and terminate at a central depot, and (b) the service trips will be assigned to a fleet of vehicles with fixed capacities and maximum allowable working durations each day, and (c) each vehicle can perform more than one service trip, and (d) the link travel times varies with vehicle travel speeds which results from congestion effects during different time of day in urban areas, and (e) the vehicles should be routed and scheduled to minimize the number of the vehicles assigned with services and the total scheduling time of all vehicles (including travel time between the nodes, waiting time and servicing time at the customers, and loading time at the central depot). The problem is formulated in a way of natural language description, which makes the formulation readable and easy to be coded. A continuous piecewise linear function is introduced to represent variation and transition of vehicle travel speeds with the time of day instead of the conventional staircase travel speed function. A solution algorithm is developed using nearest-neighbor heuristic to construct an initial solution, and using tabu search heuristic to search optimal solutions. The effectiveness of the algorithm is tested through experimental computations.

Keywords: Vehicle routing; Time-dependent; Multi-trip; Time window; Tabu search; Nearest-neighbor heuristic

1. Introduction

Vehicle Routing Problem (VRP) is one of the most challenging combinatorial optimization problems in operations research . VRP is a generic name for a whole class of problems in which a set of routes for a fleet of vehicles based at one or several depots must be determined for a number of geographically dispersed demands. The objective of the VRP is to satisfy a set of customers with known demands and minimize cost of vehicle routes originating and terminating at a depot. Many real-world problems, especially in the industries of logistics, mail, express and freight, can be described as VRPs.

In most classical