搜档网
当前位置:搜档网 › A Metaheuristic for the Pickup and Delivery Problem with Time Windows

A Metaheuristic for the Pickup and Delivery Problem with Time Windows

A Metaheuristic for the Pickup and Delivery Problem with Time Windows
A Metaheuristic for the Pickup and Delivery Problem with Time Windows

A Metaheuristic for the Pickup and Delivery Problem with Time Windows

Haibing Li and Andrew Lim

Department of Computer Science

National University of Singapore

Singapore,117543

lihaibin,alim@https://www.sodocs.net/doc/c712885121.html,.sg

Abstract

In this paper,we propose a metaheuristic to solve the pickup and delivery problem with time windows.Our ap-proach is a tabu-embedded simulated annealing algorithm which restarts a search procedure from the current best so-lution after several non-improving search iterations.The computational experiments on the six newly-generated dif-ferent data sets marked our algorithm as the?rst approach to solve large multiple-vehicle PDPTW problem instances with various distribution properties.

1Introduction

The class of Vehicle routing problems(VRP)is an inten-sive research area because of its usefulness to the logistics and transportation industry.Many new side constraints have been added to meet real life needs.A famous extension is the vehicle routing problem with time windows(VRPTW).

Another useful extension that has been proposed to VRPTW is to handle pickup and delivery where goods must be collected at a predetermined customer location before it is delivered to another speci?ed customer location.There-fore,two additional side constraints are introduced.One is known as the precedence constraint and the other one is the coupling constraint.The two constraints require that any paired pickup and delivery locations must be serviced by the same vehicle and the pickup location must be sched-uled before the corresponding delivery location in the route. Practical applications of this extension include the dial-a-ride problem,airline scheduling,bus routing,etc.

Let us de?ne the Pickup and Delivery Problem with Time Windows(PDPTW)formally.Let be a digraph.is the node set where

represents the customers and node denotes the depot where a?eet of vehicles are housed.In addition,let be the set of pickup loca-tions and be the set of delivery locations.There-fore,.Each node has an associated customer demand,a service time and a service-time window.

for and for.For each pair of nodes,a non-negative distance and a non-negative travel time are known.Due to the time window constraints,arcs may not exist between some node pairs.Therefore,the arc set can be de?ned as

.If a vehicle reaches a customer before,it needs to wait until in order to service the customer.The sched-ule duration of a route is the sum of waiting time,service time and travel time.Depending on different contexts,the problem consists of minimizing several objectives subject to a variety of constraints.For transportation of goods, the objective involves minimizing the number of vehicles, travel costs and schedule duration.However,for dial-a-ride problems,it’s preferable to minimize the inconvenience caused by pickups or deliveries performed earlier or later than desired time.In this paper,the objective of PDPTW is to service all customers without violating vehicle capac-ity,time window,precedence and coupling constraints with a minimum number of vehicles and,for the same number of routes with the minimum total travel distance,followed by the minimum total schedule duration and the minimum total waiting time.

Due to dif?culty of PDPTW,most previous works fo-cused on the single vehicle dial-a-ride problem with time windows(1-PDPTW)with slightly different objectives.For the objective to minimize the total customer inconvenience, Psara?ts[5][6]developed a dynamic programming algo-rithm with a time complexity which can solve problems with only10or fewer requests.Sexton and Bodin[9][10]solved the same problem by breaking it into a coordinating routing master problem formulated as an inte-ger program,and a scheduling subproblem for a?xed route, which was formulated as linear program.By using a heuris-tic version of Benders’decomposition,the routing master problem and the scheduling subproblem were solved indi-

vidually.Results of real problems with sizes from7to20 were reported.Sexton and Choi[11]used a similar ap-proach to minimize a linear combination of total vehicle operating time and total customer penalty due to the vio-lation of the time windows for the single vehicle pickup and delivery problem with soft time windows.For mini-mizing the schedule duration,Van der Bruggen et al.[12] developed a two-phase heuristic algorithm based on arc-exchange procedures and an alternative algorithm based on simulated annealing.Their approaches produced high qual-ity solutions on real-life problems in reasonable computa-tional time.Finally,for minimizing the total travel costs, a forward dynamic programming approach was developed by Desrosiers et al.[2].The ef?ciency of the algorithm was improved by eliminating states that were incompatible with vehicle capacity,precedence and time window con-straints.The multiple-vehicle pickup and delivery problem with time windows has received little attention.The only optimal algorithm developed by Dumas et al.[3]employed a column generation scheme with a shortest path subprob-lem with capacity,time window,precedence and coupling constraints.The algorithm can solve1-PDPTW problems up to55paired requests and multiple-vehicle PDPTW with small number of paired requests per vehicle.Recently, Willian et al.[13]proposed a reactive tabu search approach to minimize travel cost by using a penalty objective func-tion in terms of travel time,penalty for violation of over-load and time window constraints.The approach was tested on instances with sizes of25,50and100customers.These test cases were constructed from Solomon’s VRPTW benchmark instances(Solomon[7])which were solved op-timally.

In this paper,we propose a tabu-embedded simulated annealing approach to solve the general multiple-vehicle PDPTW.In addition,test cases are generated from all of the Solomon’s benchmark instances for VRPTW.

The paper is organized as follows.Section2describes the local search structures.Section3presents the meta-heuristic.The time complexity of the algorithms is ana-lyzed in Section4.Section5reports computational results for56test cases we generated from Solomon’s benchmark instances for VRPTW.Finally,we present our conclusion in Section6.

2Local Search Structures

2.1Notations

:total number of customers,total number of vehicles respectively.

:max number of iterations without improvement in annealing procedure.

:objective function of solution S of local search.

:objective function of solution S in tabu-embedded METROPOLIS PROCEDURE in the sim-

ulated annealing algorithm.

,,:total travel distance,total schedule time and total waiting time of solution S

respectively.

:neighborhood of solu-tion S obtained by PD-Shift operator,PD-Exchange

operator and PD-Rearrange operator respectively.

:local optimal solution.

:the maximum number of children in a K-ary tree.

:the depth of a K-ary tree.

:initial and global annealing temperature respec-

tively.

:cooling ratio of T.

:penalty factor for M,Dist(S),ScheTime(S), Dist(S)respectively.

2.2Route Construction Heuristics

Insertion Heuristic by Solomon[7]is modi?ed to con-struct the initial solution.During the insertion procedure, all PDPTW constraints must be satis?ed.The procedure ?rst initializes a route with a pickup-delivery(PD)paired customers,using criteria of maximal combined farthest dis-tances to depot,minimal combined latest bound of time windows and minimal combined period of time windows.

Then for each of the unrouted PD-pairs,their best feasible insertion positions in the current partially-constructed route are computed.The PD-pair which causes minimal incre-ment in travel cost is selected and inserted into the route.

Thus after all the PD-pairs are inserted,a feasible solution is obtained.

2.3Neighborhood Structures

In our method,three PD-pair swapping operators are used to de?ne local search neighborhoods.These opera-tors are PD-Shift operator,PD-Exchange operator and PD-Rearrange operator.The?rst two operators are used for generating neighborhoods for metaheuristic guided local search procedure,while the PD-Rearrange operator is only used for post-optimization purpose.

2

Figure 1.PD-Shift

Operator Figure 2.PD-Exchange Operator

2.3.1PD-Shift Operator

The PD-Shift operator moves PD-pairs from one route to another,subject to all the constraints imposed on PDPTW.For each pair of selected routes,say,Route1and Route2,the PD-Shift operator is used twice,for shifting PD-pairs from Route1to Route2and from Route2to Route1.We have denoted the neighborhood of solution S obtained by the PD-Shift operator as .In Figure 1,locations P and D are originally a PD-pair in Route1.The PD-Shift operator ?rst removes the PD-pair from Route1and then inserts them into a feasible position-pair in Route2.Infeasible shifts are forbidden with regards to the PDPTW constraints.

2.3.2PD-Exchange Operator

The PD-Exchange operator swaps PD-pairs of two routes,subject to all the constraints imposed on PDPTW.We have denoted the neighborhood of solution S obtained by the PD-Exchange operator as .In Figure 2,locations P1and D1are originally a PD-pair in Route1,while lo-cations P2and D2are originally a PD-pair in Route2.The PD-Exchange operator ?rst removes the two PD-pairs from Route1and Route2respectively,then insert P1-D1into a feasible position-pair in Route2,while insert P2-D2into a feasible position-pair in Route1.Again,infeasible ex-changes are forbidden with regards to the PDPTW con-

straints.

Figure 3.PD-Rearrange Operator

2.3.3PD-Rearrange Operator

Within the same route,the PD-Rearrange operator rear-ranges PD-pairs to the best positions that maximally reduce the value of the objective function.We have denoted the neighborhood of solution S obtained by the PD-Rearrange operator as .In Figure 3,locations P and D are a PD-pair in Route .The PD-Rearrange operator removes the PD-pair from Route ,then inserts them into a new fea-sible position-pair within the same route.Infeasible rear-rangements are also forbidden with regards to the PDPTW constraints.

2.3.4Objectives and Cost Function in Local Search In our research,we prefer the priority order of PDPTW’s objectives as follows:i)to minimize the number of vehi-cles;ii)to minimize the total travel cost;iii)to minimize the total schedule duration;iv)to minimize the drivers’total waiting time to start service.To re?ect this order of priority,we adopt the following cost function:

(1)

The penalty weight factors are set to be .Under this setting,even if the initial solutions obtained by the construction heuristic contains large number of vehicles,the number of vehicles will be reduced during the search procedure.

2.3.5Descent Local Search

As an extension of local search,descent local search(DSL)starts from an initial solution.All the solutions in the neighborhoods are checked.The best solution with the minimum objective cost assessed by (1)will act as the initial solution for repeating this DSL procedure.This is repeated until no improvement is found.INPUT :a solution S ;

OUTPUT :a local optimal solution DLS(Solution S)1.3

2.Select the best solution with minimum objective cost

within a de?ned neighborhood of

3.IF THEN

3.1;GOTO Step2

4.ELSE RETURN

3Our Metaheuristic

Metaheuristics are strategies that guide local search pro-cedures.In this section,we present a metaheuristic that guides the DSL procedure.

3.1Tabu Structure

We de?ne the following eigenvalue structure to represent a solution:

Struct Eigenvalue{

Number of vehicles(NV);

Total travel cost(TC);

Total schedule duration(SD);

Total waiting time(WT);

}

,,and will be used as table?elds in later sections.

Since the probability that two different solutions having the same eigenvalue is very small,it’s reasonable to regard two solutions as the same if they share the same eigenvalue. We record the eigenvalues of the solutions into a tabu set which differs from previous works that use edge-moves in their tabu structure.

3.2-Restarts Strategy

In our algorithm,we use a simulated annealing algorithm which differs from its traditional implementation.Instead of performing the simulated annealing procedure on the proba-bilistically accepted solution repeatedly until the procedure terminates,we compel the simulated annealing procedure to restart from the current best solution after several simulated annealing iterations without any improvement(the constant can be set to3or4to produce good results).The algorithm terminates after restarts without improvement. This acts like a rightist-ary tree.

In addition to this-restarts strategy,the visited solutions are recorded into a tabu set to avoid cycling.The hybrid metaheuristic is given below:

INPUT:a solution S;

OUTPUT:a local optimal solution

TABU EMBEDDED SA(Solution S)

1.Obtain a solution from DSL within

2.Perform a DSL within

3.

4.

5.WHILE DO

5.1Use METROPOLIS PROC(S)to obtain a fea-

sible solution S’which was not recorded in

tabu set,from the neighborhood

,record the two routes on which PD-Shift/PD-Exchange operator performed.

5.2Reduce number of vehicles by moving PD-pairs

out from one route and insert them into other

routes based on criteria of minimal increment in

objective cost.

5.3Use Solomon’s Insertion Procedure to respectively

re-order the two recorded routes of S’in step5.1.

5.4Perform a DSL within

5.5Perform a DSL within

5.6IF THEN

5.6.1;

5.7ELSE

5.8

6.RETURN

METROPOLIS PROC(Solution S)

1.WHILE NOT yet accept an neighboring solution of S

DO

1.1get a random neighbor of S which is not in

tabu set,within

1.2

1.3IF THEN

1.4ELSE

1.5IF THEN

1.5.1Accept S’

1.5.2Update global annealing temperature:

1.5.3Record S’into tabu set

2.RETURN S’

4

In METROPOLIS PROC,the cost function SACost(S)is de?ned as:

(2) Here,.In procedure TABU EMBEDDED SA,from the viewpoint of tabu search,the METROPOLIS PROC in step5.1acts as an annealing-probabilistic diversi?cation strategy to escape from local optima.In addition,Step5.3and S tep5.5act as intensi?cation strategies.In fact,the best-based-restarts strategy in the following overall algorithm itself acts as an intensi?cation strategy.

INPUT:problem data;

OUTPUT:a best solution found found

OVERALL ALGORITHMS

1.Input problem data

2.the better solution produced from Modi?ed

Solomon’s Insertion Algorithm

3.Con?gure parameters:,,,and

4.Set tabu set to be empty

5.

6.WHILE DO

6.1

6.2

6.3IF THEN

6.3.1;

6.4ELSE

7.OUTPUT

4Analysis of the Algorithms

In the above overall algorithm,K determines the stop-ping condition of the overall algorithm.The total number of iterations of local search guided by the tabu-embedded simulated annealing procedure will be,where is the depth of the rightist K-ary tree due to restarts.

In each iteration,the time complexity of the overall al-gorithm is mainly determined by the time complexity of local searches in the neighborhoods that we de?ned.Let be the overall time complexity of local searches in the neighborhoods.The ti me complexity of the whole algorithm is.

On average,each vehicle will serve customers, that is,PD-pairs.For the PD-Shift Operator,once a pickup location P in Route1is selected for swapping,

it takes time to locate its delivery counterpart D within the same rou te.Similarly,once a insertion position in Route2is determined for P,it also take time to determine another insertion position in Route2for D.In addition,there are route-pair combinations.There-fore,the time complexity for local search in is

Repeating similar analysis for,the time com-plexity of a local search in de?ned by PD-Ex-change operator is.

The rearrange operator is only used for post-optimization in the procedure of TABU EMBEDDED SA.In addition, it is only applied to the affected routes which the PD-Shift operator or PD-Exchange operator were applied.As the a bove analysis,time complexity of a local search in is.Therefore,

,since m will never be larger than n,we get.It follows that the time complexity of the whole algorithm is.As long as is kept to a small number,our running time is reason-able.

5Experimental Results

5.1Benchmark Problem Instances

We generated from Solomon’s56benchmark problem instances(See Solomon[7]),by randomly pairing up the customer locations within routes in solutions obtained by our heuristic approach for the vehicle routing problem with time windows(See Li et al.[4]).This is different from the way that William et al.[13]just paired up customers ap-pearing in the routes of the optimal solutions one by one.

In addition,we were not restricted to generating data sets using only optimal solutions.One reason is that most of the Solomon’s instances have not yet been optimally solved.

Another reason is that the PD-pairs may be much more ran-domly distributed in real life problems,so they may not nec-essarily be paired up within the same route of VRPTW so-lutions.Corresponding to Solomon’s classi?cation of,

,,,and,our data sets were also gen-erated in six classes:,,,,and .All problems have100real customers with sev-eral additional dummy nodes for coupling purpose if nec-essary,a central depot,capacity constraints,time window constraints,precedence constraints together with coupling constraints.The customers in problems are clustered.

In problems the customers are randomly distributed.In problems,customers are partially clustered and par-tially randomly distributed.The,and

problems have short scheduling horizon,while,

and have longer scheduling horizon.

5

Prob.NV TC SD CT WV WSD NC10110828.99828.935109827.3 NC10210828.99828.9130109827.3 NC10310831.910065.1156109829.9 NC1049869.510166.71539109834.7 NC10510828.99828.925109827.3 NC10610828.99828.931109827.3 NC10710827.89921.822109826.1 NC10810827.89904.839109826.1 NC10910827.89831.885109827.3 Table1.Results Obtained for Instances 5.2Computational Results

Our experimental environment is the Linux Kernel 2.2.14-5.0smp on i686.The algorithms were coded in C++ with Standard Template Library.The values of the parame-ters used are.

5.2.1Results for9problem instances

Table1shows the results obtained by our algorithms and by reactive tabu search method of William et al.[13]on the9 problems.Although our objective functions are dif-ferent,a rough comparison table is given.Here,means

CPU time in seconds,while and represent

and obtained by William et al.[13].William et al.[13] obtained7optimal solutions out of the9instances except and,by their reactive tabu search heuristic. These are very good solutions.As far as we know,Chiang et al.[14]also solved VRPTW using the same approach,but they did not reach optimal solutions for any instances. In addition,no heuristic has ever reported optimal solutions for test cases.For,our solution has a smaller number of vehicles.By comparison,our schedule durations are slightly larger than those of William et al.[13].

5.2.2Results for the newly-generated56problem in-

stances

It’s true that William et al.[13]is the?rst to solve100-customer instances,however,their experiments were con-?ned within only9instances with clustered distribution property.Because of this reason,we conduct more expe-riences on56newly-generated instances with various dis-tribution properties.Table2shows the best results obtained by our algorithms.The table lists all the4objective values in order of their priorities togther with computational times.

Prob.NV TC SD WT CT

LC10110828.949828.94033

LC10210828.949828.94071

LC10310827.8610058.03230.17191 LC1049861.9510006.90144.951254 LC10510828.949828.94047

LC10610828.949828.94043

LC10710828.949828.94054

LC10810826.449826.44082

LC10910827.829831.78 3.96255 LC2013591.569591.56027

LC2023591.569591.56094

LC2033585.569521.6626.09145 LC2043591.179591.170746 LC2053588.889588.880190 LC2063588.499588.49088

LC2073588.299660.4072.12102 LC2083588.329744.23155.91178 LR101191650.783599.45948.6587

LR102171487.573202.46714.891168 LR103131292.682729.15436.48169 LR10491013.392050.8537.46459 LR105141377.112631.56254.4569

LR106121252.622412.11159.4987

LR107101111.312220.27108.96287 LR1089968.972029.9360.96415 LR109111239.962311.3771.42348 LR110101159.352222.9963.64547 LR111101108.902189.5380.63179 LR11291003.772013.179.41638 LR20141263.843495.811231.97193 LR20231197.672749.39551.73885 LR2033949.402762.80813.401950 LR2042849.051988.57139.522655 LR20531054.022550.13496.11585 LR2063931.632502.46570.84747 LR2072903.0561936.4433.381594 LR2082734.851858.36123.513572 LR2093937.052432.61459.562773 LR2103964.222782.06817.831482 LR2112927.801954.5726.774204 LRC101141708.802956.32247.52119 LRC102131563.552764.14200.59152 LRC103111258.742443.68184.95175 LRC104101128.402238.17109.77202 LRC105131637.622830.16192.54179 LRC106111425.532475.0149.48459 LRC107111230.152344.94114.80154 LRC108101147.972245.3097.34650 LRC20141468.963358.41889.45266 LRC20231374.272657.14282.87987 LRC20331089.072700.30611.231605 LRC2043827.782537.83710.053634 LRC20541302.203464.611162.41639 LRC20631162.912444.87281.96445 LRC20731424.602461.4236.82607 LRC2083852.762271.19418.444106 Table2.Solutions for the new instances

6

Data Sets MNV MTC MSD MWT

NC19.89833.409911.7778.37

LC19.89832.089874.2042.12

LC2 3.00589.239609.7431.77

LR111.921222.202467.74245.54

LR2 2.73977.142455.75478.60

LRC111.631387.592537.22149.62

LRC2 3.251187.822736.97549.15

Table3.Statistical summary for the data sets

5.2.3Statistical summary for the data sets

The statistical computational results are shown in Ta-ble3.Here,and represents the mean values of,,and respectively.

5.2.4Route details for several selected instances Table4and Table5show the route details for several se-lected instances.The node indices larger than100indi-cate that these are dummy nodes for pairing purposes. means number of customers in the route of a vehicle.

6Conclusion

In this paper,we proposed a metaheuristic with an-nealing like restart strategy to guide the local search in three neighborhoods that we de?ned to solve the general multiple-vehicle PDPTW.This is combined with an effec-tive metaheuristic based on a restarts annealing proce-dure with tabu-list to avoid cycling in the search process.In addition,we generated56100-customer problem instances from Solomon’s benchmark instances for the vehicle rout-ing problem with time windows.The experimental results on the six different data sets marked our algorithms as the ?rst ef?cient approach to solve practical sized multiple-vehicle PDPTW problem instances with various distribu-tion properties.Furthermore,our algorithm can be easily adapted to solve further generalizations of PDPTW.

References

[1]J.Desrosiers,Y.Dumas,M.M.Solomon,and F.Sormis,

“Time Constrained Routing and Scheduling,”in Handbooks in Operations Research and Management Science:Network Routing,M.O.Ball,T.L.Magnanti,

C.L.Monma and G.L.Nemhauser Elsevier(eds),35–

139,Elsevier,Amsterdam,1995.

[2]Y.Dumas,J.Desrosiers,F.Soumis,“A dynamic pro-

gramming solution of the large-scale single vehicle

Prob.NC Details of routes

NC1041213-17-18-19-15-16-28-23-26-22-

20-24

1225-27-44-46-45-48-51-50-52-49-

47-105

1081-78-76-71-70-73-77-79-80-63

1067-65-62-74-72-61-64-68-66-69

125-3-7-8-11-9-6-4-2-1-75-104

1498-96-95-94-92-93-97-100-99-

101-14-12-10-103

1257-55-54-53-56-58-60-59-41-40-

43-42

1432-33-31-35-37-38-39-36-34-102

-29-30-21-106

1090-87-86-83-82-84-85-88-89-91 LR106865-71-51-9-35-34-3-77

663-64-11-90-10-31

1048-47-36-19-49-46-102-82-7-52

862-88-30-20-66-32-70-1

883-45-18-8-84-17-5-60

1021-72-39-23-67-55-54-4-25-101

1059-37-14-44-38-86-43-100-98-93

1050-33-29-79-81-78-68-24-80-12

896-85-91-16-61-99-6-89

1028-26-73-41-22-75-56-74-2-58

1094-92-42-15-57-87-97-104-95-13

627-103-69-76-40-53

LR2045027-52-18-7-82-48-19-11-62-88-

31-69-76-12-67-39-53-28-79-81-

9-51-20-66-65-71-35-34-78-29-

24-55-4-72-74-73-21-2-13-97-37

-98-100-91-85-93-59-96-6-89

5094-95-92-42-57-22-75-56-23-41-

15-43-14-44-38-86-16-61-99-87-

60-83-8-84-5-17-45-46-47-36-49

-64-63-90-32-10-30-70-1-50-33-

3-77-68-80-54-25-26-40-58 LR2115095-2-21-72-75-23-67-39-12-76-

29-79-33-81-9-65-71-51-30-90-

63-64-49-36-47-48-46-8-45-84-

5-6-94-96-59-37-97-13-58-26-74

-56-4-25-55-54-24-80-68-77

5028-27-52-69-31-88-62-11-19-7-

82-18-83-99-85-61-16-86-38-14

-44-98-92-87-42-43-15-57-41-22

-73-40-53-3-78-34-35-66-20-32-

10-50-1-70-60-17-91-100-93-89 Table4.Details of selected solutions

7

Prob.NC Details of routes

LRC1041214-47-15-11-9-87-59-74-102-86

-57-52

1266-106-20-49-19-23-21-48-18-25

-24-22

885-63-89-76-84-51-64-83

1069-98-53-12-17-16-13-108-10-82

1242-43-44-38-37-35-36-40-39-41-

72-54

1261-70-1-3-5-45-101-8-46-4-100-

68

890-65-99-97-75-58-103-77

1280-91-56-95-62-67-94-105-93-71

-96-81

1292-50-33-32-107-30-28-26-27-29

-31-34

1088-60-78-73-79-7-6-2-55-104 LRC1081065-83-57-24-22-49-21-23-25-77

1041-42-44-43-40-38-36-35-37-39

1069-88-61-81-94-71-72-54-96-68

1292-95-102-67-62-50-63-85-84-56

-91-80

1064-51-76-89-18-48-19-20-101-66

1082-99-52-86-87-59-97-75-58-74

1012-14-47-17-16-15-13-9-11-10

1090-53-60-7-104-6-2-70-100-55

1298-78-73-79-8-46-5-3-1-103-

45-4

1033-32-30-28-26-27-29-31-34-93 LRC2023892-95-85-63-33-28-26-27-29-31-

30-62-67-71-72-38-40-41-81-90-

91-84-49-20-83-66-56-50-34-32-

89-24-21-25-77-75-58-102

3265-82-12-14-47-15-11-69-64-19-

23-48-18-76-51-22-86-87-9-57-

52-10-97-59-74-13-17-7-4-60-

100-70

3298-45-5-3-1-42-36-37-39-44-61-

88-53-78-79-8-6-46-2-55-68-101

-43-35-54-96-93-94-80

LRC2052292-95-33-28-27-29-31-30-63-76-

85-67-84-51-49-22-20-24-74-13-

17-60

2865-83-64-19-23-21-18-57-86-52-

99-9-87-59-75-97-102-10-55-68-

43-35-37-54-96-93-91-80

302-45-5-42-39-36-72-71-62-94-61

-44-40-38-41-81-90-53-82-66-56

-50-34-32-26-89-48-25-77-58

2269-98-11-15-16-47-14-12-88-78-

73-79-7-6-8-46-4-3-1-70-100-101 Table5.(Continued)Details of selected solu-tions

dial-a-ride problem with time windows”,American

Journal of Mathematical and Management Science

16,301–325(1986).

[3]Y.Dumas,J.Desrosiers and F.Soumis,“The pick-up

and delivery problem with time windows”,European

Journal of Operational Research54,7–22(1991).

[4]H.Li, A.Lim and J.Huang,“Local Search with

Annealing-like Restarts to solve the VRPTW”,Re-

search Paper,Department of Computer Science,Na-

tional University of Singapore,(2001).

[5]H.Psara?s,“A dyanmic programming solution to the

single vehicle many-to-many immediate request dial-

a-ride problem”,Transportation Science14,130–154

(1980).

[6]H.Psara?s,“An exact algorithm for the single vehi-

cle many-to-many immediate request dial-a-ride prob-

lem”,Transportation Science17(4),351–361(1983).

[7]M.M.Solomon,“Algorithms for the vehicle routing

and scheduling problems with time window con-

strains”,Operations Research35,254–264(1987).

[8]M.W.P.Savelsbergh,M.Sol,“The general pickup and

delivery problem”,Transportation Science29(1),

107–121(1995).

[9]T.R.Sexton,https://www.sodocs.net/doc/c712885121.html,wrence,“Optimizing single vehi-

cle many-to-many dial-a-ride problem with desired

delivery time:I Scheduling”,Transportation Science

19,378–410(1985).

[10]T.R.Sexton,https://www.sodocs.net/doc/c712885121.html,wrence,“Optimizing single vehi-

cle many-to-many dial-a-ride problem with desired

delivery time:II Routing”,Transportation Science19,

411–435(1985).

[11]T.R.Sexton,Y.-Y.Choi,“Pickup and delivery partial

loads with“soft”time windows”,American Journal

of Mathematical and Management Science6,369–398

(1986).

[12]L.J.J.Van der Bruggen,J.K.Lenstra,P.C.Schuur,

“Variable-depth search for the single vehicle pickup

and delivery problem with time windows”,Trans-

portation Science27,298–311(1993).

[13]P.N.William,J.W.Barnes,“Solving the pickup and de-

livery problem with time windows using tabu search”,

Transportation Research Part B34,107–121(2000).

[14]W.-C.Chiang and R.Russel,“A reactive tabu search

metaheuristic for the vehicle routing problem with

time windows”,INFORMS Journal on Computing9,

417–430(1997).

8

相关主题