Environmental Engineering Reference
In-Depth Information
from or must be delivered to the customers. PD constraints are applied only to
customers, satellites being organised as in basic versions (1st-stage vehicles deliver
freight to satellites then 2nd-echelon vehicles pick up the corresponding goods from
them), so the VRP-PD approach is applied only for the second stage.
A particular case of 2-VRP is obtained when considering a transportation
system where taxi services are considered (2-VRP-TS). In this variant, direct
shipping from the depot or a k-stage satellite to customers is allowed if it helps to
decrease the cost, or to satisfy time and/or synchronization constraints, without
passing through the rest of the stages.
3.2 Exact Methods
Exact methods seek to find the exact optimum of the entire system, i.e. to prove
that the best solution found is optimal. The main limits of such approaches are of
two types: first is a strong simplification of the mathematical models, that assume
one depot and all satellites and vehicle fleets (for each stage) having the same
capacity; second is that the instance solved by such methods are very small (up to
5 satellites and 50 customers, according to Baldacci et al.
2013
). The first model of
this type is found in Gonzalez-Feliu et al. (
2007
) and a small set of works propose
methods to solve this problem. Branch-and-Cut (Jepsen et al.,
2013
) and Branch-
and Price (Santos et al.
2013
) allow to solve instances up to two satellites and 32
customers, although Jepsen et al.'s (2012) method obtains better results than the
others. However, a recently proposed Branch-and-Bound method (Baldacci et al.
2013
) is able to solve almost all instances up to 5 satellites and 50 customers. Such
instances, introduced in Gonzalez-Feliu et al. (
2007
) and Mancini (
2011
) are
available in the OR-library of Beasley (
1990
).
3.3 Systemic Heuristic Approaches
According to Gonzalez-Feliu (
2013b
), two types of heuristics are proposed to
solve such problems. The first is that of systemic approaches that see the multi-
stage transport problem as a whole system and the second includes methods that
separate the problem into a set of sub-problems, one per stage, that are solved
separately. Concerning systemic approaches, they need to deal with simplified
problems, in a similar way than exact methods, in order to be deployed but allow
finding near-optimal solutions for bigger instances, some of them being near to
real size problems. According to Mancini (
2013b
) we can group those heuristics in
different categories. We adapt this classification to city logistics problems.
First is that of construction heuristics, which aim to find initial solutions. In
other words, such algorithms find a sub-optimal solution to the problem and stop
once the first feasible solution is found. Although they are far from theoretical
Search WWH ::
Custom Search