International Journal of Artificial Intelligence p-ISSN: 2407-7275, e-ISSN: 2686-3251 Original Research Paper Solving Rich Vehicle Routing Problem Using Three Steps Heuristic Ismail Yusuf Panessai1.
Mohd.
Sapiyan Baba1.
Nur Iksan1 Program of Artificial Intelligence.
Faculty of Computer Science and Information Technology.
University of Malaya.
Kuala Lumpur.
Malaysia.
Article History Received:
Revised:
Accepted:
*Corresponding Author:
Ismail Yusuf Panessai Email:
Ismailyusuf.
panessai@yahoo.
Abstract: Vehicle Routing Problem (VRP) relates to the problem of providing optimum service with a fleet of vehicles to customers.
It is a combinatorial optimization problem.
The objective is usually to maximize the profit of the operation.
However, for public transportation owned and operated by government, accessibility takes priority over profitability.
Accessibility usually reduces profit, while increasing profit tends to reduce In this research, we look at how accessibility can be increased without penalizing the profitability.
This requires the determination of routes with minimum fuel consumption, maximum number of ports of call and maximum load factor satisfying a number of pre-determined constraints: hard and soft constraints.
To solve this problem, we propose a heuristic algorithm.
The results from this experiment show that the algorithm proposed has better performance compared to the partitioning set.
This is an open access article, licensed under: CCAeBY-SA Keywords: Genetic Algorithm.
Ship Routing Problem.
VRP.
2014 | International Journal of Artificial Intelligence | Volume.
1 | Issue.
1 | 1-19
Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Introduction The vehicle routing problem (VRP) is a general combinatorial optimization problem that has become a key component of transportation management.
The VRP was first introduced in .
The general VRP consists of determining several vehicle routes with minimum cost for serving a set of customers, whose geographical coordinates and demands are known in advance.
Each customer is required to be visited only once by one vehicle.
Typically, vehicles are homogeneous and have the same capacity General VRP is defined on a connected graph G.
Let G = (V.
A) be a graph where V is a set of nodes .
and A is the set of arcs .
Let C = .
be a cost matrix associated with A.
The matrix C is said to be symmetric when cij = cji and asymmetric otherwise.
The vehicle must start and finish its tour at the depot and the problem is to construct routes at minimum travel cost.
VRP lies between travelling salesman problem (TSP) and the bin packing problem (BPP).
The travelling salesman needs to visit each city exactly once, starting and ending his travel in his/her home The problem is to find the shortest tour through all cities.
In a graph model.
TSP is required to find the shortest tour which visits all specified disjointed subsets of the vertices of a graph.
combinatorial optimization, the TSP is a NP-hard.
The BPP is described as follows: given a finite set of numbers .
he item size.
and a constant specifying the capacity of the bin, determine the minimum number of bins needed where all items have to be inside exactly one bin and the total capacity of items in each bin has to be within the capacity limits of the bin.
In BPP, objects of different volumes must be packed into a finite number to suit the bins vehicle capacity in a way that minimizes the number of bins used.
In computational complexity theory, the BPP is a combinatorial NP-hard problem.
The abbreviation NP-hard refers to nondeterministic polynomial time hard.
That means that it is not guaranteed that there is a known algorithm that solves all cases to optimality in a reasonable execution time.
So in addition of an appropriate solution approach, a number of heuristics and metaheuristics have been developed to find a solution to the problem.
To describe the TSP as a VRP we take an instance of the VRP with one depot, one vehicle with an unlimited capacity .
r set all demands to zer.
, a cost function proportional to only the distance, and an arbitrary number of customers .
Similarly to describe the BPP as a VRP we consider the variant of the VRP with one depot and a cost matrix of all zeroAos.
For literature reviews of TSP and BPP, readers are referred to .
, 3, 4, 5, 6, 7, .
Literature Review This section briefly discusses the ship routing problem and methods to solve the problem have been proposed for VRP in earlier research.
Ship Routing Problem The VRP may actually be considered a broad class of routing problems and it is an important research in the area of transportation.
The geographic location of a region will affect the efficiency of the transportation system.
In archipelagic countries with long shorelines or many wide rivers, ship transportation plays a significant role in domestic trade.
For the wider situation, ship transportation is the major conduit of international trade.
The VRP is composed of many specific variants i.
multi depot VRP, capacitated VRP, symmetric VRP etc.
For many cases, a combination of two or more of these variants for solving a real world problem was needed.
The varieties of VRP with similarities in the ship routing problem are as shown in Table 1.
A MDVRP is a general VRP with multiple depots.
A company may have several depots from which it can serve its customers.
If the customers are clustered around depots, it is possible to model this distribution problems a set of MDVRP.
The objective of the MDVRP is to serve all customers while minimizing the number of vehicles and the sum of travel time.
The feasible solution of MDVRP would be to make each route satisfy the VRP constraints while beginning from and returning to the same depot.
Lau et al.
proposed MDVRP as follows, as each depot stores and supplies various products, and has a number of identical vehicles with the same capacity to serve customers who demand different quantities of various products.
Each vehicle starts the tour from its resided depot, delivers Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
products to a number of customers, and returns to the same depot.
The objective of the VRP in their paper is to minimize the total cost due to the total distance travelled of all vehicles and due to the total time required for all vehicles to serve customers, subject to a number of constraints.
Table 1.
Variety VRP with Similarities in Ship Routing Problem
Variety VRP
Heterogeneous fleet VRP
(HVRP)
Site dependent capacitated VRP (SDCVRP) Multi depot VRP (MDVRP) Asymmetric VRP (AVRP) Description Ships operate with different sizes, types and capacity.
Sea depth of each port may be different.
the ship draft should not be equal to or greater than the sea depth.
Each ship serves exactly one route and the route must include at least one fuel port where the number of fuel ports is more than one.
Distance for sailing from port i to port j and port j to port i may be different.
Lau et al.
proposed to use a stochastic search technique while Salhi & Sari .
and Nagy & Salhi .
used a heuristic method to solve MDVRP.
Salhi & Sari .
presented a multi level composite heuristic and introduced two reduction tests, i.
within depot reduction test and between depot reduction tests to enhance the efficiency of the proposed heuristic.
Nagy and Salhi .
proposed an integrated heuristic method which included four phases: .
find a weakly feasible initial .
improve on the solution while maintaining weak feasibility.
make the solution strongly feasible.
improve on the solution while maintaining strong feasibility.
Renaud et al.
and Cordeau et al.
proposed to solve MDVRP using tabu search.
Renaud et .
solved the problem by using a tabu search algorithm which comprised three phases i.
e, fast improvement, intensification, and diversification.
Each of these phases utilized some or all of the three basic procedures, 1-route, 2-route, and 3-route mechanism.
While Cordeau et al.
proposed a tabu search heuristic consisting of the GENI heuristic which was used to insert unrouted customers or remove customers from their current routes and then reinsert them into different routes.
Skok et al.
and Jeon et al.
used a metaheuristic method to solve MDVRP.
Skok et al.
used general GA with roulette wheel selection in which six crossover operations and three mutation operations were examined.
Their research found that the cycle crossover and fragment reordering crossover were superior to the others while scramble mutation outperformed other mutation Jeon et al.
proposed a hybrid GA with some features which are: .
produce the initial population by using both a heuristic and a random generation method.
minimize infeasible solutions instead of elimination.
gene exchange process after mutation.
flexible mutation rate.
route exchange process at the end of GA.
The CVRP is the most common and basic variant of the VRP.
CVRP is a generic name given to a whole class of problems in which each vehicle has the same loading capacity, starts from only one depot and then routes through to customers.
A set of routes for a fleet of vehicles based a depot at must be determined for a number of geographically dispersed customers, and vehicles have the maximal loading capacity.
All customers have known demands for a single commodity and each customer can only be visited by one vehicle, and each vehicle has to return to the depot.
The service time unit can be transformed into the distance unit.
The loading and travelling distance of each vehicle cannot exceed the loading capacity and the maximum travelling distance of the vehicle.
All vehicles in CVRP are homogeneous, having the same capacity while the size of the fleet is There are many variants of the CVRP that relax one or both of these conditions.
One variant of the CVRP is the heterogeneous fleet vehicle routing problem (HVRP).
In HVRP, the fleet is composed of a fixed number of vehicles with a difference in their equipment, capacity, age or cost and in which the number of available vehicles is fixed as a priori .
The decision is how to best utilize Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
the existing fleet to serve customer demands.
In the HVRP, the transportation cost of a vehicle is proportional to the distance travelled.
VRP intensifies in the real-life context when the vehicle fleet is heterogeneous.
The use of a heterogeneous fleet of vehicles has multiple advantages.
In some cases it is possible to service customers requiring small vehicles because of accessibility restrictions.
Notable examples are size and weight constraints which may even vary over time, as exemplified by a shipAos physical dimension constraints, including ship draft restrictions that vary with tide, available berth space in ports and sea depth of ports.
In the heterogeneous fleet, vehicles of different carrying capacities give the flexibility to allocate capacity according to the customerAos varying demands in a more cost effective way, by deploying the appropriate vehicle types to areas with the analogous concentration of customers.
HVRP can be solved by mathematical methods, heuristic and meta-heuristic.
Tarantilis et al.
solved HVRP by implementing a threshold accepting procedures where a worse solution is only accepted if it is within a given threshold, and they provided an improved version in .
While.
Yaman .
put forward six formulations which are enhanced by valid inequalities and lifting.
Choi & Tcha .
present a linear programming relaxation which is solved by the column generation technique.
Choi & .
used a column generation technique which is enhanced by dynamic programming schemes.
and Pessoa et al.
proposed a Branch-Cut-and-Price algorithm over an extended formulation that is capable for solving HVRP.
Gendreau et al.
and Taillard .
used a heuristics to solve HVRP.
Taillard .
proposed an algorithm based on tabu search, adaptive memory and column generation, a heuristic column generation method in which a tabu search requiring node coordinates is used to generate a large set of routes and a solution is obtained by solving a set partitioning problem whose columns correspond to these routes.
Prins .
developed an algorithm based on heuristics, which followed a local search procedure based on the steepest descent local search and tabu search while Dondo & Cerda .
developed a three phase heuristic.
Penna et al.
proposed an iterated local search based on a heuristic method.
Subramanian et al.
proposed a hybrid algorithm that was composed of an iterated local search based on a heuristic method and a set partitioning formulation.
The set partitioning model was solved by means of a mixed integer programming solution that interactively calls on the iterated local search heuristic during its execution.
A metaheuristic method is used to solve HVRP in Ochi et al.
and Li et al.
Ochi et al.
presented an evolutionary hybrid meta-heuristic which combines a parallel Genetic Algorithm with scatter search while Li et al.
published a record-to-record travel metaheuristic.
Prins .
used a memetic algorithm to solve HVRP.
SDCVRP is a variant of the HVRP where there exists a dependency between the type of vehicle and the customer, meaning that not every type of vehicle can serve every type of customer because of site-dependent restrictions .
, 31, 32, .
AVRP is a variant of the VRP where travel distance from i to j may be different with j to i.
AVRP
is related to the asymmetric travelling salesman problem (ATSP).
It is a generalized travelling salesman problem in which distance between a pair of cities need not be equal in the opposite The ATSP is an NP-hard problem, thus many meta-heuristic algorithms have been proposed to solve this problem, such as a hybrid genetic algorithm .
and a tabu search proposed .
The aim of the general VRP is to minimize total travel time or travel distance that contributes to the cost.
In particular, fuel cost for different types and sizes of fleet is also studied to minimize the fuel consumption .
, .
Heuristic Algorithm for Solving VRP Many methods to solve the problem have been proposed for VRP.
Some research efforts were oriented towards the development and analysis of approximate heuristic techniques capable of solving real VRP problems.
Bowerman et al.
classified the heuristic approaches to the VRP into five Cluster first and route second Route first and cluster second Savings and insertion Improvement and exchange Simpler mathematical programming representations through relaxing some constraints.
Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Novoa et al.
developed a heuristic algorithm based on the maximum insertion concept to solve VRP while Pertiwi .
used a set covering heuristic to solve ship routing problem.
The solution approach consists of two steps, the first step is generating ship routes and the second step is choosing the best ship routes.
Pertiwi .
adopted a nearest neighbour method for generating ship routes.
The nearest neighbour method compares the distribution of distances that occur from a point to its nearest neighbour.
Nearest neighbour starts with a randomly chosen port and adds the nearest but not yet visited port to the last port in the tour until all the ports are visited.
Problem Description This research is on a heterogeneous fleet of passenger ships.
The ship starts the tour from the depot and visit all the ports assigned before returning to the depot.
Fuel Consumptions In this research a model is proposed for calculating total fuel consumption of route combinations for the heterogeneous fleet where the fuel consumption of each vehicle depends on the type of vehicle.
Generally, fuel consumption of the ship is related to the type of engine used.
The fuel consumption of a ship is given by Eq.
f ijk A A * P k * AI k * t ijk * A tijk A .
= Fuel consumption of ship k = Voyage time for ship k sailing from port i to port j = Distance travelled for ship k sailing from port i to port j.
lij may be different from lji = Speed of ship k = Constant .
= Engine power of ship k (HP) = Number of engine = Efficiency .
k The following is an example.
Suppose a depot v0 serves three customers: 1, 2, 3 with two mix fleet k1 and k2.
The total distance of the route: .
is 270 miles.
The speed of k1 is 19 knots and that of k2 is 17 knots where the number of engines used is 1, respectively, whilst the power of k1 is 8,700 HP and k2 is 2,176 HP.
Based on Eqs.
1 and 2, the fuel consumption of k1 is 15,825.
18 litres and k2 is 4,424 litres.
It shows that although the ships serve the same route, travel costs are not the same because their fuel consumptions are not equal.
Constraints The vehicle fleet tends to be mixed as the vehicle types are slightly different.
This implies that the ships are of different capacity, speed and cost.
Basically, there are two types of constraints: soft and hard constraints.
Soft Constraints There are two soft constraints for the ship routing problem:
Ship draft and sea depth If the ship-draft is equal to or more than the sea depth then it is anchored a few miles from the port.
This incurs additional cost to carry passengers and cargo from ship to port and from port to ship.
Thus, the ship draft should not be equal or greater than the sea depth.
Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Load factor Ships with a large capacity should serve ports with more passengers to reduce costs due to the load The load factor between two ports is calculated by Eq.
A ijk bijk A .
Where:
= Load factor for ship k sailing from port i to port j = Number of passengers in ship k sailing from port i to port j = Capacity of ship k Soft constraint is dealt with by imposing a penalty if a route exceeds the limit.
The penalties imposed are:
Ship draft and sea depth: 500 litres when ship draft is equal to or more than the sea depth.
Load factor: imposed penalty 5000 litres for load more than 100%, imposed penalty 1000 litres for load factor less than 50% and imposed penalty 500 litres for load factor betweens 50% to 75%.
Hard Constraints Hard constraints are dealt with by removing unfeasible routes.
Hard constraints in the ship routing problem include:
Travel time The maximum duration for each tour is called commission days.
T k .
Hence a ship must return to the depot within T k .
If Trk is the shipAos travel time, then Trk C T k .
Trk is calculated by Eqs.
E lijk
E E l kji
Tijk A E k A t kj E A E k A tik E
E Ev
E E
Trk A Tijk A (TijkA1 ) .
= Total voyage time by ship k Tijk = Travel time by ship k sailing from port i to port j and stays in port i added travel time for sailing from port j to port i and stays in port j.
= Distance travelled by ship k sailing from port i to port j.
lij may be different from lji t ik = Port time of ship k that stays in port i Travel distance Each ship has a different fuel tank size, hence the maximum distance.
Lk that is travelled is This distance must be equal to or greater than the total distance of the route r.
Lkr , i.
Lkr C Lk .
Lk is calculated by Eq.
while Lkr is calculated by Eqs.
- (.
Lk A A k * vk A * Pk * AIk * A .
A .
k * .
Lkij A lijk A l kji Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Lkr A Lkij A ( Lkij A1 ) = Distance travelled by ship k sailing from port i to port j.
lij may be different from lji Lkr = Total distance travelled for route r served by ship k = Maximum allowed routing distance for ship k = Speed of ship k = Constant .
= Engine power of ship k (HP) AIk = Number of engines used in ship k = Efficiency .
= Maximum capacity of the shipAos tank Fuel port A route must include at least one fuel port.
Mathematical Model Let.
G = (P.
A) be a graph, where P = .
, 2, .
M N} is the index set of ports .
and A = {.
, .
iC i, j.
i < .
is the set of arcs .
Every arc .
, .
is associated with a distance matrix L= lijk , which represents the asymmetric travel distance from port i to port j, i.
, lij is not necessary equals to lji.
In order to present the mathematical formulation of the models, we used the following:
Notation C is the index set of customer ports.
C = .
, 2.
M} D is the index set of fuel ports.
D = .
, 2.
N} K is the index set of ships.
K = .
, 2.
S} Parameter hi = Sea depth of port i vk = Speed of ship k A k = Ship draft of ship k f ijk = Fuel consumption for ship k sailing from port i to port j T k = Maximum allowed routing time .
ommission day.
for ship k = Distance travelled by ship k sailing from port i to port j.
lij not necessary equals to lji bijk = Load factor for ship k sailing from port i to port j = Seat capacity of ship k gijk = Number of passengers in ship k, travelling from port i to port j Yrk = Number of ports of call of ship k when serving route r Decision variables C xrk,ij A E if ship k sailing from port i to port j at route r C denotes the penalties when ship draft of ship k is equal to or more than the sea depth of port i Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
E2000
A AE
A k C hi
C denotes the penalties of the load factor of ship k when sailing from port i to port j
E5000
E2000
A AE
E1000
bijk A 100 bijk A 50 50 C bijk A 65 C denotes the penalties of the number of ports of call when ship k serve route r E2000 Yrk A 15 A A E1000 15 C Yrk C 20 Problems arise to construct a route with minimum fuel consumption in a feasible set of routes for each vehicle.
The feasible route for ship k is to serve ports without exceeding the constraints:
Total travel time Trk for any vehicle is no longer than T Total travel distance Lkr for any vehicle is no longer than L The feasible route must include at least one fuel port The mathematical formulation is given in Eq.
Eu f ij .
xr ,ij A Eu Eu k EaK i , jEaP Eu A .
xr , ij A Eu k Ea K i , jEa P Eu A .
xr ,ij A A Eu Y r k Ea K i , jEa P k EaK The objectives is to minimize the sum of the fuel consumption on the routes travelled, the penalty cost for violations of the ship draft and sea depth, the penalty cost for violations of the load factor and the penalty cost for violations of the number of ports of call.
Subject to:
All ports .
ustomer and fuel port.
i are serviced by ship k at least once .
Eu Eu xr ,ij C 1 .
Ai Ea P.
Ak Ea K k EaK iEaP Travel time of ship k is not longer than the maximum allowed routing time T k Eu Tr C T .
kEaK Total distance travelled for route r served by ship k is not longer than the maximum allowed routing distance of ship k Eu Lr C L k EaK Ship draft of ship k must be less than the sea depth of port i .
Eu Eu A k A hi k EaK iEaP Route r served by ship k should possess a fuel-port k EaK i , j .
DEaP D .
xrk,ij C 1 Solution Procedure This research proposes using a heuristic algorithm to find the optimal route and vehicle assignment.
The goals are to minimize conflicts between accessibility and profitability.
The accessibility is affected by maximum number of ports of call while profitability is affected by minimum fuel consumption and maximum load factor.
The feasible route combination should meet the requirements:
C Each route is served by one ship C Each port is served at least once C Each route has at least one fuel port C Each ship has total travel time within 14 days C Each ship does not exceed the allowed travel distance Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Figure 1.
Clustering Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Figure 2.
Assigning Vehicle Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Figure 3.
Finding Best Routes A route is considered optimal when: there is low fuel consumption, the number of ports of call is high and the load factor is about 65%-100%.
This research uses heuristic method which Aocluster first and route secondAo adopted for solving four VRP variants.
It involves three phases for the method i.
clustering, assigning of vehicle and finding the best routes by combining feasible solution.
Three phases for the algorithm are:
Phase I: Clustering Routes are clustered to solve the problem based on the constraint: travel time and travel distance allowed for each route.
Travel time is less or equal to the maximum travel time allowed and the travel distance is less or equal to the maximum travel distance allowed.
The output is a feasible route set for the solution candidate.
Phase II: Assigning vehicle Vehicles are assigned in a cluster to ensure each route has at least one fuel port and route is removed if this condition is violated.
In this phase, fuel consumption is calculated with a penalty imposed if the shipAos draft is equal to or greater than the sea depth, penalty is imposed for the load factor conditions while penalty is imposed for the number of ports of call conditions.
Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Phase i: Finding best routes A robust algorithm is developed based on the maximum-insertion concept where the heuristic model with the maximum-insertion concept is modified and the idea is to successively insert a route into the best combination of routes with minimum fuel consumption.
The output is a set of optimum routes with minimum fuel consumption and the selected routes must satisfy the following conditions:
C All ports are served at least once.
C All ships are used.
C Each route must be serviced only by one ship C Total fuel consumption is the lowest possible.
Experiments All computational experiments are carried out using an Intel(R) Core(TM) i5 CPU M430 @2.
27GHz.
Benchmarks Problem The experiment described herein examined the performance of the proposed algorithms compared to the partitioning sets heuristic in 11 benchmarks.
Benchmarks are generated based on the existing routes in PT.
PELNI (PELNI, 2.
that represent different performances.
All the benchmarks can be seen in Table 2.
Table 2.
Benchmarks Generated Based On the Existing Route in PT.
PELNI (PELNI, 2.
Benchmarks Number of Customer Fuel Vehicles Ports Ports 40c-9d-8k 28c-9d-9k 45c-11d-11k 32c-4d-8k 34c-11d-11k 63c-14d-11k 18c-6d-8k 28c-6d-11k 12c-4d-8k 53c-12d-11k 24c-5d-10k Represent of Routes served by ships where capacity is 1000 - 1500 seats Routes where the number of ports of call is 10 15 Routes where the number of ports of call is 16 20 Routes where the number of ports of call is 20 and above Routes where the number of ports of call is 16 and less Routes where the number of ports of call is 17 and above Routes where the number of ports of call is 13 Routes with the highest number of fuel ports .
Routes where the number of fuel ports is more than the number of customer ports Routes where the number of fuel port is 6 or Routes where the number of fuel port is 7 Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Result Table 3 shows the best known solution using partitioning sets in 11 benchmarks while Table 4 shows performance of the routes and generated by proposed algorithms.
The proposed algorithm consists of three steps i.
clustering, assigned vehicle and choose route with minimum fuel consumption.
Table 3.
Best Known Solution Using Partitioning Sets In 11 Benchmarks 40c-9d-8k Best known solution (Partitioning set.
Fuel
Number of Load
Consumption Ports of Call
Factor
1,275,883
28c-9d-9k
2,375,323
45c-11d-11k
3,868,567
32c-4d-8k
1,036,758
34c-11d-11k
2,743,105
63c-14d-11k
4,755,085
18c-6d-8k
1,491,149
28c-6d-11k
2,134,324
12c-4d-8k
1,263,833
53c-12d-11k
2,945,322
24c-5d-10k
1,267,387
Benchmarks Number of Customer Fuel Vehicles Ports Ports The computational result is given in Table 4.
Table 4.
Solution of 11 Benchmarks Solved By Proposed Algorithm
40c-9d-8k
Proposed Algorithm
Fuel
Number of Consumption Ports of Call
1,067,352
28c-9d-9k
1,900,067
45c-11d-11k
3,029,397
32c-4d-8k
888,475
34c-11d-11k
2,177,213
63c-14d-11k
3,699,584
18c-6d-8k
1,231,551
28c-6d-11k
1,716,760
12c-4d-8k
1,060,131
Benchmarks Number of Customer Fuel
Vehicles Ports Ports 53c-12d-11k
2,328,848
24c-5d-10k
1,061,950
Load Factor Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Analysis Summaries of the fuel consumption of each algorithm can be seen in Table 5.
Table 5.
Fuel Consumption of 11 Benchmarks Benchmarks 40c-9d-8k
28c-9d-9k
45c-11d-11k
32c-4d-8k
34c-11d-11k
63c-14d-11k
18c-6d-8k
28c-6d-11k
12c-4d-8k
53c-12d-11k
24c-5d-10k
TOTAL
Fuel Consumption Partitioning Sets Proposed Algorithms 1,275,883 2,375,323 3,868,567 1,036,758 2,743,105 4,755,085 1,491,149 2,134,324 1,114,330 2,945,322 1,267,387 25,007,233 1,067,352 1,900,067 3,029,397 888,475 2,177,213 3,699,584 1,231,551 1,716,760 1,060,131 2,328,848 1,061,950 20,161,328 The minimum fuel consumption used to serve all ports in 11 benchmarks is routes generated by the proposed algorithm.
Increased efficiency fuel consumption of the hybrid genetic algorithm compared to the PELNI method (PELNI, 2.
calculated by Equation .
Efficiency A | 20,161,328 - 25,007,233 | 25,007,233 .
Efficiency = 19.
Based on Equation .
, increased efficiency fuel consumption of the routes generated by proposed algorithms compared to the routes generated by partitioning sets is 19.
Based on fuel consumption, the performance of the proposed algorithm shows better performance than the partitioning sets.
Summaries of the number of ports of call of each algorithm can be seen in Table 6.
The percentage of the solution obtained by the proposed algorithm compared to partitioning sets algorithm is calculated using Equation .
Efficiency A | 506 - 1516 | .
Efficiency = 66.
Based on Equation .
the decreased number of ports of call of the proposed algorithm compared to the partitioning sets algorithm is 66.
Based on the number of ports of call.
the performance of routes generated by partitioning sets shows better performance than the proposed algorithms.
For the average of the load factor results tabulated in Table 7.
From Table 7 it can be seen that the average of the load factor of routes generated by partitioning sets is about 4.
48% while the average of the load factor of the routes generated by proposed algorithm is about 23.
Based on the load factor, the performance of the proposed algorithm shows better performance than the partitioning sets.
Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Table 6.
Number of Ports of Call (NPC) of 11 Benchmarks Benchmarks 40c-9d-8k
28c-9d-9k
45c-11d-11k
32c-4d-8k
34c-11d-11k
63c-14d-11k
18c-6d-8k
28c-6d-11k
12c-4d-8k
53c-12d-11k
24c-5d-10k
TOTAL
Number of Ports of Call (NPC) Partitioning Sets 1,516 Proposed Algorithms Summaries of the load factor of each algorithm can be seen in Table 7.
Table 7.
Load Factor of 11 Benchmarks Benchmarks 40c-9d-8k
28c-9d-9k
45c-11d-11k
32c-4d-8k
34c-11d-11k
63c-14d-11k
18c-6d-8k
28c-6d-11k
12c-4d-8k
53c-12d-11k
24c-5d-10k
TOTAL
Load factor Partitioning Sets Proposed Algorithms As aforementioned in the first chapter, the objective function in this research is to minimize conflicts between accessibility and profitability.
Accessibility is associated with the number of the ports of call while profitability is associated with the load factor.
The goal of increasing profit will contradict the goal of greater accessibility.
Since the goal is to minimize conflicts of interest between accessibility and profitability then we propose a measurement tool called Aoquadrant scaleAo.
The quadrant scale consists of load factor for x axis and number of ports of call for y axis.
There are 4 areas in quadrant scale:
C I is the area for high accessibility but low profitability C II is the area for high accessibility and high profitability Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
i is the area for low accessibility but high profitability IV is the area for low accessibility and low profitability Based on data presented in Table 5.
Table 6 and Table 7, the quadrant scale of each algorithm is shown in Figure 4.
From the Figure 4, routes generated by partitioning sets is spread in quadrant I and IV.
7 out of 11 benchmarks are in quadrant IV, it means that the number of ports of call and the load factor are low.
The routes generated by partitioning sets shows worst performance.
Figure 4 shows routes generated by proposed algorithm are spread between quadrant i and IV.
Generally we can say that the best performances of 11 benchmarks are the routes generated by the proposed algorithm.
Figure 4.
Quadrant Scale of Each Algorithm in 11 Benchmarks Ismail Yusuf Panessai.
Mohd.
Sapiyan Baba.
Nur Iksan.
Solving Rich Vehicle Routing Problem Using Three Steps Heuristic.
International Journal of Artificial Intelligence, vol.
1, no.
1, pp.
December 2014.
DOI: 10.
36079/lamintang.
Conclusion VRP is composed of many specific variants i.
multi depot VRP, capacitated VRP, symmetric VRP Similarly, the variety VRP in the ship routing problem in our case study are MDVRP.
HVRP.
SDVRP and AVRP then it is called rich VRP.
To solve this problem, we propose an algorithm with three phases for the method i.
clustering, assigning of vehicle and finding the best routes by combining feasible solution.
To evaluate the algorithm, an experiment is carried out.
The experiment is to investigate the performance of the proposed algorithm over 11 benchmarks.
The result from this experiment shows that the proposed algorithm has better performance compared to the partitioning sets algorithm.
All result can be summarized as:
A The increased efficiency fuel consumption of the routes generated by proposed algorithms compared to the routes generated by partitioning sets is 19.
Based on fuel consumption, the performance of the proposed algorithm shows better performance than the partitioning A The decreased number of ports of call of the proposed algorithm compared to the partitioning sets algorithm is 66.
Based on the number of ports of call.
the performance of routes generated by partitioning sets shows better performance than the proposed algorithms.
A The average of the load factor of routes generated by partitioning sets is about 4.
48% while the average of the load factor of the routes generated by proposed algorithm is about 23.
Based on the load factor, the performance of the proposed algorithm shows better performance than the partitioning set.
Acknowledgment This work was supported in part by the University of Malaya under Grant RG078-ICT 2011.
References