《物流系统分析与优化》课程教学课件（PPT讲稿）ACO-TS for VRPTW

ACO-TS for VRPTW

ACO-TS for VRPTW

. The VRP with time windows (VRPTW) includes a time window [e, I]forthe depot andfor eachcustomerv,(i=O,...,n)during whichthecustomerhas to be served (with eobeing theearliest starttime and lthelatest returntimeofeachvehicletothedepot)

• The VRP with time windows (VRPTW) includes a time window [ei , l i ] for the depot and for each customer vi (i = 0,., n) during which the customer has to be served (with e0 being the earliest start time and l0 the latest return time of each vehicle to the depot)

. The objective is to find the routes of minimum cost, where:for every vehicleroute,the totaldemand does not exceed the capacityof thevehicle,·all vehicle routes begin and end at the depot,:every customeris visitedexactly oncebyexactly onevehicle,:allcustomersarevisited,:thetime when the vehicle arrives at every customershould be within therequiredtime

• The objective is to find the routes of minimum cost, where • for every vehicle route, the total demand does not exceed the capacity of the vehicle, • all vehicle routes begin and end at the depot, • every customer is visited exactly once by exactly one vehicle, • all customers are visited, • the time when the vehicle arrives at every customer should be within the required time

Notationsthe linkfromcustomeritoiisvisited by vehiclekXikotherwise0tis the arrival time at customeri:w,is thewait timeat customer i:Kis thetotal number of vehicles:Nis the depot and customers set;C, is the length on the link from customeritoj:t,is travel time be-tween customeriand j:qiis thequantityof thegoods to bedeliv-ered at customeri:Qis the capacity of a vehicleeis the earliestarrival timeat customer i:l,is the latest arrival time at customeri:Siistheservicetimeatcustomeri:Tkisthemaximumroutetimeallowedforvehiclek

Notations

NK2克2Min1-0101-k=1NKX<Kfori=-o(a)NNXik≤1fori=oke(1.....K) (b)HWA(c)forie(1,...N)Xgk=1j=oj-iZXk=1(d)forje(1...,N)-is.t.NNEq(e)Xk≤Qforke(....K)E-Oj-x(g+ ) T(f)forke(1...,K)(g)to=Wo=So=0(h)Xjk=Xk(ti+tg+$,+w.)<tforje(1....N)k=1-o1-j(0)forie(1....N)ei<(t+w)<l

The objective is to minimize the total travel length under sev-eral constraints:(a)the maximum number of routesconstraintb)travelconstraints,candd)serviceconstraints,(e)thecapacityconstraint,(fthe maximum travel time constraint and (g-i)thetimewindows constraints.For more details see(Tanet al.,2oo1a2001b)

ACO-Tabu·Solutionrepresentation8Fig, 1, A typical vehide routing problem.Fig 2.Sequence code ofthe solution from Fig1

ACO-Tabu • Solution representation

·SolutionconstructionLetU(k)denotesthesetofunvisited nodesofantkandtheantislocatedatcustomeri.Thus,toselectthenextcustomerinthecon-struction graph,theantk uses thefollowingprobabilistic rule:[g]"x[n,)jU(k)Zhuk,la"x1a(2)py(k)0otherwisewhere,pi(k)is the probability of choosingto combinecustomersiandjon theroute:Tiis thepheromonedensityof edge(i.j):nuisthevisibility of edge(i,j):α and βis the relative influence of thepheromonetrails and the visibility values,respectively.Here,α=2andβ=1:Tabu=thesetof theinfeasiblenodesforthekth ant

• Solution construction

·Neighborhood searchTheneighborhoodsearchisconductedbychangingcustomernodesofoneortworoutesinasolutionxchangirOld021570346089100old021570346089100Exchanging021580346079100New21503460879100Fig3,Exchanging two customersbetween two routesFig.4.Inserting a customer into anther route

• Neighborhood search • The neighborhood search is conducted by changing customer nodes of one or two routes in a solution

: 2-opt exchange221DDO3344FiG.1. Exchange of links (1,2), (3, 4) for links (1, 3), (2,4)

• 2-opt exchange