Real Applications

Metaheuristics like ant colony optimization (ACO) can be used to solve

combinatorial optimization problems. In this paper we refer to its successful application
to the vehicle routing problem (VRP). At the beginning, we introduce the VRP and
some of its variants. The variants of VRP were designed to reproduce the kind of
situations faced in the real-world. Further, we introduce the fundamentals of ant colony
optimization, and we present in few words its application to the solution of the VRP. At
the end, we discuss the applications of ACO to a number of real-world problems: a VRP
with time windows for a major supermarket chain in Switzerland; a VRP with pickup
and delivery for a leading distribution company in Italy and an on-line VRP in the city
of Lugano, Switzerland, where clients’ orders arrive during the delivery process.

The Vehicle Routing Problem

The vehicle routing problem can be designed as a combinatorial optimization
problem: Finding optimal routes for a fleet of vehicles performing assigned tasks on a
number of geographically sectored clients. An answer to this problem is the best route
serving all clients using a fleet of vehicles, respecting all operational constraints, such as
vehicle capacity and the driver’s maximum working time, and minimizing the total
transportation cost.

Optimization Framework Inspired By Ants

Ant colony optimization [5] is a metaheuristic inspired by the observation, made
by ethologists, that ants are able to find the shortest path to a food source by laying and
following chemical trails. The chemical substance which ants use to communicate
information regarding the shortest path to food is called pheromone. Communicate
means that a moving ant lays some pheromone on the ground, thus marking a path with
a trail of this substance. In the majority of cases an isolated ant moves randomly and
when it discovers a previously laid pheromone trail it can decide, with high probability,
to follow it, thus reinforcing the trail with its own pheromone.

Major supermarket chains:

Distribution of goods from inventory stores to shops
In this business case one of the major supermarket chains in Switzerland has the
following challenge: Palletized goods must be distributed to more than 600 stores, all
over Switzerland. To replenish their local stocks each store orders daily quantities of
goods, which have to be delivered within time windows. So each store can plan and
allocate efficiently according to the daily availability of its personnel and the time
requested for inventory management tasks. Further there are three types of vehicles:
trucks (capacity: 17 pallets), trucks with trailers (35 pallets), and tractor units with semi-
trailers (33 pallets).
 Important vehicle routing problems.

Comparison of the man-made vs. the computer-generated tours in the VRPTW

application

Solution method and results

This planning challenge was modeled as a VRPTW, and solved by an
implementation of the MACS-VRPTW algorithm [9], named ANTROUTE. MACS-
VRPTW is the most efficient ACO algorithm for the VRPTW and one of the most
efficient metaheuristics overall for this problem. ANTROUTE adds to MACS-VRPTW
the ability to handle the choice of the vehicle type: at the start of each tour the ant
chooses a vehicle. To prevent vehicles arriving too early at the stores a waiting cost was
also introduced. The central idea of the MACS-VRPTW algorithm is to use two ant
colonies (MACS stands for multi ant colony system) to optimize two objectives: One
colony, named ACS-VEI, minimizes the vehicles while the other one, named ACS-
TIME, minimizes time.

Major logistics operator:

Distribution from factory to inventory stores
In this business case the company is a major logistics operator in Italy. The
distribution process comprises moving palletized goods from factories to inventory
stores, before they are after distributed to shops. A customer in this vehicle routing
problem is either a pick-up or a delivery point. A central depot doesn’t exist, and
approximately 1000 –1500 vehicles per day are used.
Solution method and results
This planning challenge was modeled as a VRP with pickup and delivery and
time windows (VRPPDTW). The objective function quantifies the average tour
efficiency. The ANTROUTE algorithm for using in this context has been modified:
Since for this problem there is a single objective instead of two (business case before)
— to maximise average efficiency — the ant colony minimising the number of vehicles
was removed.
Fuel oil distributor:
On-line VRP for fuel distribution
This case study treats a fuel oil distribution company in Switzerland, which
serves its customers from its main depot located near Lugano with a fleet of 10 trucks.
The fuel oil distributor noted that during every Winter season there was always a subset
of their customers that ran out of fuel and had to place urgent orders. These
unanticipated orders have an impact on the planned delivery routes of the trucks, and
the vehicle routing problem becomes very “dynamic”. This means that a considerable
percentage of orders must be fulfilled after the trucks have already left the depot. The
goal of this case study was to evaluate the impact of a reactive strategy for vehicle
routing, starting from data analysis collected in periods when urgent deliveries were in
high request. A sample of 50 customers from the company data base was randomly
selected and travel times among them were computed. In the company records,
customers randomly appeared during the working day with random requests for a
quantity of fuel to be supplied.

Solution method and results

The problem description above fits the on-line VRP variant, where new orders
can be allocated to vehicles which have already left the depot (e.g., parcel collection,
feeder systems, fuel distribution, etc.). Montemanni et al. [17] have developed an ACO-
inspired algorithm, ACS-DVRP, adapted from the decomposition of the on-line VRP
into a sequence of static VRPs. ACS-DVRP solves the on-line fuel oil distribution
problem and its algorithm architecture consists of three main elements: the event
manager, the ant colony algorithm and the pheromone conservation strategy. The event
manager obtains new orders and maintains track of the already served orders and of the
position and the remaining capacity of each truck. This information is used to build the
sequence of static VRP-like instances. The working day is split into time slices and for
each of them a static VRP is created. Every static VRP considers all the already
received (but not yet executed) orders. New orders received during a time slice are
deferred until its end. At the end of each time slice, customers whose service time starts
in the next time slice are assigned to the trucks. They will not be considered in the
following static VRPs.

Conclusions
This contribution describes the metaheuristic ant colony optimization and how it can be
successfully used to solve a number of variants of the basic vehicle routing problem.
The main part presents two industrial-scale applications of ACO for the solution of
static VRP problems: a VRP with time windows and a VRP with pickup and delivery.
Then the contribution focuses its attention on one important dynamic variant of the
VRP: the on-line VRP. The problem is receiving increasing attention based on its
relevance to real world problems, in particular for distribution in urban environments.
The applications of ACO on real-world VRP shows that this metaheuristic inspired by
ants has become an important tool in applied operations research.
To see all problem check:
Rizzoli, Andrea-Emilio & Montemanni, Roberto & Lucibello, Enzo & Gambardella,
Luca Maria. (2007). Ant colony optimization for real-world vehicle routing problems.
Swarm Intelligence. 1. 135-151. 10.1007/s11721-007-0005-x.
Or
https://www.researchgate.net/publication/220058891_Ant_colony_optimization_for_rea
l-world_vehicle_routing_problems