A Soft Computing-Based Idea Applied to the Truck and Trailer Routing Problem

Introduction

Intelligent transport systems are advanced applications which, aim to provide innovative services relating to different modes of transport and traffic management and enable various users to be better informed and make safer, more coordinated, and 'smarter' use of transport networks. Vehicle Routing Problem, VRP, is a generic name given to a whole class of problems where it is needed to design a set of routes. In the VRP a fleet of vehicles has to be routed from one or several depots to serve a set of geographically dispersed cities or customers, subject to side constraints. The goal is to design vehicle routes originating from and terminating at the central depot to fulfill each customer’s demand so that the total cost is minimized. The total demand on each route should not exceed the vehicle capacity and each customer can only be serviced once by exactly one vehicle (Toth & Vigo, 2002). There exists a wide variety of VRPs and a broad literature on this class of problems. The most important problems are: VRP with Time Windows (VRPTW), VRP with Backhauls (VRPB), VRP with Pick-Up and Delivery (VRPPD) and Capacitated VRP (CVRP).

Recently has been defined the Truck and Trailer Routing Problem (TTRP), an extension of the VRP that adds the use of trailers. In the standard TTRP, a set of customers with known demand is serviced by a fleet of vehicles (truck pulling a trailer) with known capacity. However, due to practical constraints, including government regulations, limited maneuvering space at customer site, road conditions, etc., some customers may only be serviced by a truck. All these characteristics generate different types of routes in a TTRP solution. These routes originating from and terminating at a central depot and they are limited by capacity of vehicle used.

TTRP is a combinatorial optimization problem and it is computationally more difficult to solve than VRP. It's worth noting, in the nature of the TTRP is patent the presence of vague, imprecise and inexact information such as the demand of customers, the distances between customers, the capacities of the vehicles or the windows time. For such a reason will be convenient to solve this problem using techniques of Soft Computing (Verdegay et al., 2008). The aims of the present paper are: a) to provide a study on the Truck and Trailer Routing Problem that serves as help to researchers interested on this topic; b) to present an approach using techniques of Soft Computing to solve this problem. The paper is organized as follow: Section Background gives a review of the related problems with TTRP and its definition. Also describes the formal definition of the TTRP, comments some variants and methods used to solve this problem, and a Soft Computing based approach is finally presented as general method to face the uncertainty in their data.