Discrete Optimization
A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints
Stephen C.H.Leung a ,Zhenzhen Zhang b ,Defu Zhang b ,⇑,Xian Hua b ,Ming K.Lim c
a
奥巴马就职演说
Department of Management Sciences,City University of Hong Kong,Hong Kong b
Department of Computer Science,Xiamen University,Xiamen 361005,China c
Derby Business School,University of Derby,Derby,UK
a r t i c l e i n f o Article history:
Received 18October 2011Accepted 16September 2012Available online 3October 2012Keywords:Routing Packing
Simulated annealing Heterogeneous fleet
a b s t r a c t
The two-dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP)is a variant of the classical vehicle routing problem in which customers are rved by a heterogeneous fleet of vehicles.The vehicles have different capacities,fixed and variable operating costs,length and width in dimension,and two-dimensional loading constraints.The objective of this problem is to minimize transportation cost of designed routes,according to which vehicles are ud,to satisfy the customer demand.In this study,we propod a simulated annealing with heuristic local arch (SA_HLS)to solve the problem and the arch was then extended with a collection of packing heuristics to solve t
he loading constraints in 2L-HFVRP.To speed up the arch process,a data structure was ud to record the information related to loading feasi-bility.The effectiveness of SA_HLS was tested on benchmark instances derived from the two-dimensional loading vehicle routing problem (2L-CVRP).In addition,the performance of SA_HLS was also compared with three other 2L-CVRP models and four HFVRP methods found in the literature.
Ó2012Elvier B.V.All rights rerved.
1.Introduction
The vehicle routing problem (VRP)was firstly addresd by Dantzig and Ramr (1959),proposing the most cost-effective way to distribute items between customers and depots by a fleet of vehicles.Taking into account of the attribute of the fleet,the tra-ditional VRP has evolved to different variants.Amongst them in-clude CVRP (homogenous VRP)that only considers a constraint of vehicles having the same limited capacity (Rochat and Taillard,1995),HVRP (heterogeneous VRP)that rves customers with dif-ferent types of vehicles (Golden et al.,1984;Gendreau et al.,1999;Lima et al.,2004;Prins,2009;Brandao,2011),VRPTW (VRP with time windows)that requires the rvice of each customer to start within the time window subject to time windows constraints (Kol
en et al.,1987);and SDVRP (split deliver VRP)that allows more than one vehicle rving a customer (Chen et al.,2007).Readers are to refer to Crainic and Laporte (1998)and Toth and Vigo (2002)for a detailed description of VRP and its variants.To solve the VPR variants above effectively,a number of metaheuristics have been applied,such as simulated annealing (Osman,1993),Tabu arch (Brandao,2011;Gendreau et al.,1999),genetic algorithms (Lima et al.,2004),variable neighborhood arch (Imran et al.,2009),
and ant colony optimization (Rochat and Taillard,1995;Li et al.,2009).
In the real world,logistics managers have to deal with routing and packing problems simultaneously.This results in another domain of VRP to be investigated.In the literature,there are a number of frameworks propod to address the two problems simultaneously.Iori et al.(2007)addresd the VRP with two-dimensional packing constraints (2L-CVRP)with an algorithm bad on branch-and-cut technique.Gendreau et al.(2008)propod a Tabu arch heuristic algorithm to solve large instances with up to 255customers and more than 700items in the 2L-CVRP.Zachariadis et al.(2009)developed a new meta-methodology guided Tabu arch (GTS)which can obtain better results.In this work,a collection of packing heuristics was propod to check the loading feasibility.Fuellerer et al.(2009)prented a new ant colony optimization algorithm deriving fr
om saving-bad ant colony opti-mization method and demonstrated its performance to successfully solve the 2L-CVRP.More recently,Leung et al.(2011)developed a new efficient method that consists of a ries of algorithms for two-dimensional packing problems.The method has proven its capability to improve the results of most instances ud by Zachariadis et al.(2009).Duhamel et al.(2011)propod a GRASP ÂELS algorithm for 2L-CVRP,whereby the loading constraints were transformed into resource constrained project scheduling problem (RCPSP)constraints before a packing problem can be solved.However,only basic CVRP and Unrestricted version
0377-2217/$-e front matter Ó2012Elvier B.V.All rights rerved.dx.doi/10.1016/j.ejor.2012.09.023
Corresponding author.Tel.:+865922582013;fax:+865922580258.
E-mail address:dfzhang@xmu.edu (D.Zhang).
of2L-CVRP were solved with their algorithm.Some rearchers have extended their heuristics to three-dimensional problems. Gendreau et al.(2006)propod a multi-layer Tabu arch algorithm that iteratively invokes an inner Tabu arch procedure to arch the optimal solutions of a three-dimensional loading sub-problem.Tarantilis et al.(2009)ud a guided Tabu arch (GTS)approach w
ith a combination of six packing heuristics to solve 3L-CVRP.In their work,a manual unloading problem was also tested.Furthermore,Fuellerer et al.(2010)also propod their methods to deal with three-dimensional loading constraints.In addition,Iori and Martello(2010)provided a review in regard to vehicle routing problems with two and three-dimensional loading constraints.
Since most enterpris own a heterogeneousfleet of vehicles or hire different types of vehicles to rve their customers,it is there-fore crucial to study VRP with afleet of heterogeneous vehicles.The heterogeneousfleet VRP(HFVRP)address the VRP with a hetero-geneousfleet of vehicles which have various capacities,fixed costs and variable costs(Choi and Tcha,2007;Imran et al.,2009).In the literature,three versions of HFVRP have been studied.Golden et al. (1984)considered the variable costs to be uniformly spread across all vehicle types and the availability of each type of vehicle to be unlimited.Gendreau et al.(1999)considered the different variable costs for different types of vehicle.The third HFVRP was introduced by Taillard(1999)and Tarantilis et al.(2004),in which the number of available vehicles of each type is limited.Recently,Penna et al. (2011)introduced an Iterated Local Search,combined with a Vari-able Neighborhood Decent procedure and a random neighborhood ordering(ILS-RVND),to solve all variants of HFVRP.
In this paper,we combined the HFVRP with two-dimensional loading constraints,called the heterogen
eousfleet vehicle routing problems with two-dimensional loading constraints(2L-HFVRP). However,to the best of our knowledge,no work has been con-ducted to address such VRP although it is a practical problem in real-world transportation and logistics industries.In2L-HFVRP, there are different types of vehicles with different capacity,fixed cost,variable cost,length and width in vehicle dimension,and
two-dimensional loading constraints.The demand of a customer is defined by a t of rectangular items with given width,length and weight.All the items belonging to one customer must be as-signed to the same route.The objective is to describe the minimum transportation costs with a function of the distance travelled,fixed and variable costs associated with the vehicles.
This paper prents a simulated annealing(SA)algorithm for 2L-HFVRP.In the literature SA has been proven to be an effective method to solve combinatorial optimization problems and it has been successfully applied to2L-CVRP(Leung et al.,2010).In this paper,a heuristic local arch is ud to further improve the solu-tion of SA.In addition,six promising packing algorithms,whereby five were developed by Zachariadis et al.(2009)and one by Leung et al.(2010),are also ud to solve the loading constraints in 2L-HFVRP.The algorithms are extensively tested on benchmark instances derived from the2L-CVRP test problems with vehicles of different capacity,fixed and variable costs,le
ngth,and width. The comparison with veral effective methods of the2L-CVRP and pure HFVRP is also given.
2.Problem description
The2L-HFVRP is defined on an undirected connected graph G=(V,E),where V={0,1,...,n}is a vertex t corresponding to the depot(vertex0)and the customers(vertices1,2,...,n)and E={e ij:i,j2V}is an edge t.For each e ij2E,a distance d ij (d ii=0)is associated.Afleet of P different types of vehicles is lo-cated at the depot,and the number of vehicles of each type is unlimited.Capacity Q t,fixed cost F t,variable cost V t,length L t and
width W t are associated to each type of vehicle t(t=1,2,...,P). The loading surface of vehicle of type t is A t=L tÃW t.On the basis that a vehicle with larger capacity usually has higher cost and greater fuel consumption,we assume that Q16Q26ÁÁÁ6Q P,F1-6F
2
6ÁÁÁ6F
P
and V16V26ÁÁÁ6V P.The traveling cost of each
edge e ij2E by a vehicle type t is C
ij t
¼V tÃd ij.The transportation cost of a route for vehicle type t is C R¼F tþ
P i<j R j
i¼1
V tÃd RðiÞ;Rðiþ1Þ, where R is the route who start point and end point are the depot. Each customer i(i=1,2,...,n)demands a t of m i rectangular items,denoted as IT i,and the total weight of IT i equals to D i.Each item I ir2IT i(r=1,2,...,m i)has a specific length l ir and width w ir.We also denote a i¼
P m i
r¼1
w irÃl ir as the total area of the items of customer i.In2L-HFVRP,a feasible loading must satisfy the fol-lowing constraints:
亲爱的英文怎么说(i)All items of a given customer must be loaded on the same
vehicle and split deliveries are not allowed.
(ii)All items must have afixed orientation and must be loaded with their sides parallel to the sides of the loading surface. (iii)Each vehicle must start andfinish at the depot.
(iv)Each customer can only be rved once.
(v)The capacity,length and width of the vehicle cannot be exceeded.
(vi)No two items can overlap in the same route.
The objective of2L-HFVRP is to assign customer i(i=1,2,...,n) to one of the routes,so that the total transportation cost is mini-mized and all the routes fulfill the constraints.In this paper,we
200S.C.H.Leung et al./European Journal of Operational Rearch225(2013)199–210
consider two versions of2L-HFVRP which is the same as2L-CVRP: the Unrestricted only deals with feasible loading of the items unto the vehicles,and the Sequential considers both loading and unload-ing when visiting a customer,his/her items can be unloaded without the need to move items that belong to other cus-tomers in the same route).Fig.1gives an example of the two versions.
单身英文3.The optimization heuristics for two-dimensional loading problems
For a given route,it is necessary to determine whether all the items required by the customers can be feasibly loaded onto the vehicle.In this paper,we willfirst investigate if the total weight of items demanded by the customers exceeds the capacity of the vehicle.Otherwi,six packing heuristics are ud to solve the two-dimensional loading problem.As mentioned earlier,the load-ing position of an inrted item must be it must not lead to any overlaps(for both Unrestricted and Sequential prob-lems),or quence constraint violations(for Sequential only).The firstfive heuristics Heur i(i=1,2,...,5)are bad on the work by Zachariadis et al.(2009).Each heuristic loads an item in the most suitable position lected from the feasible ones according to the individual criterion as follows:
Heur1:Bottom-leftfill(W-axis).
The lected position is the one with the minimum
W-axis coordinate,breaking ties by minimum L-
axis coordinate.
Heur2:Bottom-leftfill(L-axis).
The lected position is the one with the minimum
L-axis coordinate,breaking ties by minimum W-
axis coordinate.
Heur3:Max touching perimeter heuristic.
The lected position is the one with the maximum
sum of the common edges between the inrted
item,the loaded items in the vehicle,and the load-
ing surface of the vehicle.
Heur4:Max touching perimeter no walls heuristic.
The lected position is the one with the maximum
sum of the common edges between the inrted
item and the loaded items in the vehicle.
Heur5:Min area heuristic.
The lected position is the one with the minimum
nand flashrectangular surface.The rectangular surface corre-
sponding to the position at the circle point is shown
on the left in Fig.2.
More details of thefive heuristics can be found in
Zachariadis et al.(2009).In order to handle a more
complex system Heur6was also ud,which was
propod in Leung et al.(2010).
Heur6:Maxfitness value heuristic.
二年级下册数学题100道口算
This heuristic gives a priority to a loading point if it
can decrea the number of corner positions when
we place an item on the point.As a result,every
time an item is loaded,we will lect the best load-
winter什么意思ing point for the item,which would increa the
probability to obtain a better loading position.
The six heuristics are called in quence,which means if Heur1fails to produce a feasible loading solution,the more com-plex Heur i(i=2,...,6)will be called one at a time tofind the solu-tion.If a feasible solution is found,the loading process stops and the solution is stored.
During the loading process,feasible loading positions are recorded.Atfirst,only the front left corner(0,0)is available.When an item is successfully inrted,four new positions are added onto the list,and the occupied and duplicated positions are removed.As shown in Fig.2,item D is inrted in the position shown by a circle and four new positions are created.
The items are loaded one at a time according to a given quence.Here,two orders(Ord1,Ord2)are generated.In a given route,each customer has a unique visit order.Ord1is produced by sorting all items by rever customer visit order,and breaking ties by decreasing area.In Ord2,all items are simply sorted by decreasing area.Both orders will be evaluated by the six heuristics to arch for feasible loading solutions.The pudo-code for the packing heuristics is given in Table1.
4.The simulated annealing meta-heuristics for2L-HFVRP
Simulated annealing(SA)is a point-bad stochastic optimiza-tion method,which explores iteratively from an initial solution to a better result(Cerny,1985;Kirkpatrick et al.,1983).The arch mechanism o
f SA has a very good convergence,and it has been widely applied in solving various NP-hard problems.Each iteration
Table1
The pudo-code for the packing heuristics.
Is_Feasible(Route r)
if total weight of all items exceeds the capacity then
return fal
end if
sort the items to generate two orderings Ord1,Ord2
for each ordering Ord i of the two orderings do
if Heur1k Heur2k Heur3k Heur4k Heur5k Heur6then
return true
end if
end for
return fal
Table2
The pudo-code of SA_HLS for the2L-HFVRP.
SA_HLS_2L-HFVRP(customer demands,vehicle information)
Generate initial Order through sorting the customers by decreasing total
weight
Assign_Vehicle(Order)to construct the initial solution
T k=T0,Iter=0//Iter is the number of iteration
while stopping criteria not met do
for i=1to Len do
if Iter<10then
generate a new Order bad on the old one
Assign_Vehicle(new Order)
if the new solution is packing-feasible and better than the current
one then
accept the new solution as current solution
end if
accept the new Order bad on the acceptance rule of SA
play onend if
stochastically lect NS from{NS1,NS2,NS3},then get a feasible solution
if new solution is better than the current one then
accept the new solution as the current solution
el
accept the new solution through the acceptance probability function
end if
Local_Search(),and get a new feasible solution
if new solution is better than the best one then
replace the current solution with this new one
end if
update the best solution when the solution is better than it
end for
T k=0.9ÃT k,Iter=Iter+1
end while
return the best solution
S.C.H.Leung et al./European Journal of Operational Rearch225(2013)199–210201
选择题口诀in SA generates a candidate solution using a neighborhood func-tion.This is a vital step to develop an efficient SA.However,in many cas,the neighborhood function alone is inadequate when eking for a global optimum solution.In addition to the propod SA,we also u heuristic local arch algorithms to improve the
solutions.Therefore,our algorithm is denoted as SA_HLS.Some mechanisms are adopted to adjust the arch trajectory.
One important characteristic of SA is that it can accept a wor solution on a probabilistic manner,aiming to arch for a better re-sult.With the initial temperature T 0,the temperature cooling sche-dule is T k =0.9ÃT k À1.For a specific temperature T k ,a quence of moves are carried out,which is a Markov chain who length is de-noted as Len .In every iteration,after applying the nei
ghborhood function,if the new solution is better than the current solution (i.e.the cost is lower),then it is accepted.However,if the cost is higher,the new solution may be accepted subject to the accep-tance probability function p (T k ,S new ,S cur ),which depends on the difference between the corresponding cost values and the global parameter T k :
p ðT k ;S new ;S cur Þ¼exp
cos t ðS cur ÞÀcos t ðS new Þ
k
公司乔迁
ð1Þ
where S cur and S new reprent the current solution and the new solu-tion respectively.Table 2provides a framework for the propod SA_HLS methodology.4.1.Initial solution
Good initial solutions are often a key to the overall efficiency of the metaheuristic.We construct the initial solution focusing on the demand of the customers,so that the u of different
types
Table 3
The pudo-code for assigning customers into vehicles.
Assign _Vehicle (Order )iud [1,2,...,P ]={0}
for each customer i in Order do while true do
lect the vehicle k which is not tabu for i and has minimum (freeD k ÀD i )ÃF k
inrt the customer i at the last position of route for vehicle k if !Is_Feasible (route )then
iud [P ]=iud [P ]+1;//add a new vehicle with largest capacity Tabu this vehicle k for customer i el
if freeD k <MinD then //vehicle k cannot rvice any customer
iud [t ]=iud [t ]+1//assuming the type of vehicle k is t ,add one
new vehicle
end if
accept the new route,and break the loop//start to assign successive customer
end if end while end for
return generated solution
Table 4
The characteristics of items of Class 2–5instances.Class
m i
Vertical Homogeneous Horizontal Length
Width Length Width Length Width 2[1,2][0.4L ,0.9L ][0.1W ,0.2W ][0.2L ,0.5L ][0.2W ,0.5W ][0.1L ,0.2L ][0.4W ,0.9W ]3[1,3][0.3L ,0.8L ][0.1W ,0.2W ][0.2L ,0.4L ][0.2W ,0.4W ][0.1L ,0.2L ][0.3W ,0.8W ]4[1,4][0.2L ,0.7L ][0.1W ,0.2W ][0.1L ,0.4L ][0.1W ,0.4W ][0.1L ,0.2L ][0.2W ,0.7W ]5
[1,5]
[0.1L ,0.6L ]
[0.1W ,0.2W ]
[0.1L ,0.3L ]
[0.1W ,0.3W ]
[0.1L ,0.2L ]
[0.1W ,0.6W ]
202S.C.H.Leung et al./European Journal of Operational Rearch 225(2013)199–210
of vehicles can be maximized.Firstly,all of the n customers are sorted on decreasing value of D i(i=1,2,...,n),where D i is the total demand of customer i(i=1,2,...,n)and the quence is re-corded as Order.Subquently we assign the customers one at a time from the Order list to a vehicle.The decision of which vehi-cle is assigned to a given customer is bad on the least value of (freeD kÀD i)ÃF k,where freeD k is the unud capacity and F k is the fixed cost of the current vehicle k(procedure Assign_Vehicle()). Becau the number of each type of vehicle is unlimited,the pro-cedure alwaysfinds a feasible solution.Table3provides a pu-do-code for the propod Assign_Vehicle()algorithm.iud is an array prenting the number of ud vehicles of different types.MinD is the minimal demand in all the customers.When assigning one customer i to vehicle k,the feasibility is examined to ensure the loading for the modified route is feasible.Other-wi,the assignment of customer i to vehicle k is forbidden and the procedure tries to assign the customer i to
another vehicle.
As shown in Table2,this procedure is ud in SA.In each loop, a partial gment of Order is reverd to get a new Order.Then, we reassign the customers using this method.If a new solution is better than the current one,it becomes the new current solu-tion in order to adjust the arch trajectory.This is assumed that previous solution does not have a good characteristic that can be improved easily.In order to obtain a better solution,the new Order is adopted bad on the SA acceptance rule.After veral steps of improvement by SA,the solution constructed is usually not comparable to the current one.So this method is only applied during thefirst ten iterations.
乱七八糟英文
Table5
Datat for different types of vehicle.
Inst A B C D
Q A L A W A F A V A Q B L C W C F C V C Q C L C W C F C V C Q D L D W D F D V D
120101010 1.025151520 1.140252530 1.260402040 1.3 220101010 1.025151520 1.140252530 1.355402040 1.5 320101010 1.030151520 1.160402040 1.2
420101010 1.040202020 1.160402030 1.2
51000101010 1.025******** 1.14000252530 1.36000402050 1.5 62000101010 1.025******** 1.14000402030 1.3
7200101010 1.0500151520 1.120002525120 6.0450040202508 8200101010 1.0500151520 1.120002525120 5.04500402025010 920101010 1.025151520 1.148402030 1.3
10200101010 1.0500151520 1.1200025251208.04500402025010 11200101010 1.0500151520 1.1200025251208.04500402025010 1220101010 1.025151520 1.140402030 1.3
132000101010 1.05000151550 2.030,000402020010
14500101010 1.01500151550 2.130002020400 3.2500040208005 155******** 1.01500151550 2.130002020400 3.2500040208005 1620101010 1.040202020 1.160402030 1.2
1720101010 1.025151520 1.140252530 1.360403040 1.4 182******** 1.0500202030 2.020********* 5.0
1920101010 1.040201020 1.160201530 1.2150402090 5.0 202000101010 1.04000201020 1.11
0,000301560 4.030,00040201508 2120101010 1.040201020 1.160201530 1.220040201208 2220101010 1.040201020 1.160201530 1.220040201208 2320101010 1.040201020 1.160201530 1.220040201208 2420101010 1.040201020 1.160201530 1.2100402060 3.2 2520101010 1.040201020 1.160201530 1.220040201208 2620101010 1.040201020 1.160201530 1.220040201208 2720101010 1.040201020 1.160201530 1.2100402060 3.2 2820101010 1.040201020 1.160201530 1.220040201208 29200101010 1.0500201030 2.0200040201208.0
3020101010 1.040201020 1.160201530 1.220040201208 3120101010 1.040201020 1.160201530 1.220040201208 3220101010 1.040201020 1.160201530 1.220040201208 3320101010 1.040201020 1.160201530 1.220040201208 3420101010 1.040201020 1.160201530 1.220040201208 35200101010 1.0400201020 1.51000402060 4.0
36100101010 1.020******* 1.1300302030 1.2400402040 1.3
Table6
Calibration experiment result for T0and Len.
5152535
S Sec tot S Sec tot S Sec tot S Sec tot
T0
Unrest5266.65327.945159.32288.995094.74402.305111.83500.08 Seq5427.43461.795274.77510.395198.10580.955238.46680.85
3000500070009000
Len
Unrest5144.37383.375094.74402.305078.97779.145083.18968.25 Seq5328.87456.855198.10580.955206.401025.195191.071242.93
S.C.H.Leung et al./European Journal of Operational Rearch225(2013)199–210203
