Article Preview
Top1. Introduction
According to Zitz (2010) “The efficient routing of objects is of significant importance in our modern society. Several aspects of routing affect us on a daily basis regardless if we think about it or not. Whether it is browsing the internet, sending mail, transporting consumer goods, or simply travelling, routing is involved. Recent developments in the world economy, as well as increased interest in environmental concerns, justify the application of efficient techniques to solve complicated routing problems. Benefits include lowering cost expenditures as well as possibly reducing pollution from vehicles, but also introducing time wise gains since routes may potentially be shortened”
For the aforementioned reason the route planning is one of the most studied research topics in the operations research area. While the standard Vehicle Routing Problem (VRP) is the classical problem formulation. The term VRP is a generic name given to a whole class of problems where it is needed to design a set of routes. There exists a wide variety of VRPs and a broad literature on this class of problems. Recently has been defined the Truck and Trailer Routing Problem (TTRP) that consist in the use of trailers; a commonly neglected feature in the VRP. The TTRP is a combinatorial optimization problem and is computationally more difficult to solve compared with the VRP.
In the literature the use of trailers in vehicle routing problems has so far received little attention, even though it has a high practical application. The beginning TTRP is guided by the fact that the specific requirements of real life should be added in the classical model. It is necessary a model able to represent the additional features that exist in many practical applications. For example, the use of different types of vehicles or restrictions on access by customers, etc.
In the standard TTRP, a set of customers with known demand is serviced by a fleet of vehicles with known capacity. Vehicles can be a truck pulling a trailer called complete vehicle or a vehicle without a trailer called pure truck. The use of truck alone is due to practical constraints such as government regulations, limited maneuvering space at customer site, road condition, etc. The TTRP considers two forms of customer types: a customer who is accessible with or without a trailer is called a vehicle customer (VC) and one who is only accessible without a trailer is called truck customer (TC). The access to a TC implied leaves the trailer in a parking place, called the root of sub-tour.
There are three types of routes in a TTRP solution. The Figure 1 shows the three types of routes in a TTRP solution. These types of routes originating from and terminating at a central depot and they are limited by capacity of vehicle used.
Figure 1. Routes types in the TTRP. (Adapted from Lin, Yu, and Chou, (2009))
The types of routes are:
- •
Complete Vehicle Route (CVR): Consisting of a main tour performed by a complete vehicle visiting strictly VCs and at least one sub-tour in which the trailer is detached at a vehicle customer location, to visit (with the truck alone) TCs and VCs. A sub-tour starts and ends at the parking place where the trailer was de-coupled.
- •
PureTruck Route (PTR): Is a route performed by a truck without trailer are visited both customer type. Thus a customer on the route may be a TC or a VC.
- •
Pure Vehicle Route (PVR): Is a route performed by a complete vehicle serving only VC. In this route the trailer is never uncoupled.
The TTRP can be reduced to the VRP if there are no TCs. Therefore, the TTRP is at least as difficult as the VRP which is NP-Hard. The main alternative to solve this class of problems is using approximate algorithms; due to that are believed to be hard in general, by exploring the usually large solution search space. Therefore, has been developed specific heuristics and metaheuristics for to solve the TTRP.