Competitive Analysis for Dynamic Multiperiod. Uncapacitated Routing Problems Enrico Angelelli and M. Grazia Speranza, страница 11

A natural extension of this research is to investigate an asymptotic lower bound on the competitive ratio of any online algorithm for T tending to infinity and to analyze the performance of SMART and its time-dependent variant for longer planning horizons.

We have assumed that orders have to be fulfilled within the next two time periods. In the near future, we plan to investigate the impact of that restriction, i.e., whether significantly differentresultsareobtainedwhenmorethattwotimeperiods are available to fulfill orders.

Wehaveignoredsomekeyaspectsofthemotivatingapplication, most glaringly everything related to the size of orders and the limited capacity of the vehicles that deliver orders. As a result, the routing problem to be solved in each time period is a traveling salesman problem. Capacitated variants of the DMPRP deserve to be studied.

Finally, establishing the competitive ratio of an on-line algorithm provides only partial information on its performance. We also plan to study, theoretically as well as empirically, optimal and suboptimal policies under a probabilistic characterization of the demand.

REFERENCES

[1]  G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, and M. Talamo, Algorithms for the on-line travelling salesman, Algorithmica 29 (2001), 560–581.

[2]  R. Bent and P. Van Hentenryck, Scenario-based planning for partially dynamic vehicle routing with stochastic customers, Oper Res 52 (2004), 977–987.

[3]  D.J. Bertsimas and D. Simchi-Levi, A new generation of vehicle routing research: Robust algorithms, addressing uncertainty, Oper Res 44 (1996), 286–304.

[4]  D.J. Bertsimas and G. Van Ryzin, A stochastic dynamic vehicle routing problem in the Euclidean plane, Oper Res 39 (1991), 601–615.

[5]  M. Blom, O Krumke S., W.E. de Paepe, and L. Stougie, The online TSP against fair adversaries, INFORMS J Computing 13 (2001), 138–148.

[6]  M. Dror, G. Laporte, and P. Trudeau, Vehicle routing with stochastic demands: Properties and solution algorithms, Transport Sci 23 (1989), 166–176.

[7]  M. Gendreau, F. Guertin, J.Y. Potvin, and P. Taillard, Parallel tabu search for real-time vehicle routing and dispatching, Transport Sci 33 (1999), 381–390.

[8]  G. Ghiani, F. Guerriero, G. Laporte, and R. Musmanno, Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies, Eur J Oper Res 151 (2003), 1–11.

[9]  S. Ichoua, M. Gendreau, and J.Y. Potvin, Diversion issues in real-time vehicle dispatching, Transport Sci 34 (2000), 426–438.

[10]  S. Irani, X. Lu, and A.C. Regan, On-line algorithms for the dynamic traveling repair problem, J Scheduling 7 (2004), 243–258.

[11]  P. Jaillet and M. Wagner, On-line routing problems: Value of advanced information and improved competitive ratios, Transport Sci 40 (2006), 200–210.

[12]  S.O. Krumke, W.E. de Paepe, D. Poensgen, and L. Stougie, News from the online traveling repairman, Theor Comp Sci 295 (2003), 279–294.

[13]  A. Larsen, O.B.G. Madsen, and M.M. Solomon, Partially dynamic vehicle routing models and algorithms, J Oper Res Society 53 (2002), 637–646.

[14]  S.Mitrovic-Minic,R.Krishnamurti,andG.Laporte,Doublehorizon based heuristics for the dynamic pickup and delivery problem with time windows, Transport Res Part B 38 (2004), 669–685.

[15]  H.Psaraftis,Dynamicvehicleroutingproblems,Vehiclerouting: Methods studies, B. Golden and A. Assad (Editors), North Holland, Amsterdam, 1988, pp. 223–248.

[16]  D.SleatorandR.E.Tarjan,Amortizedefficiencyoflistupdate and paging rules, Commun ACM 28 (1985), 202–208.

[17]  B.W. Thomas and C.C. White III, Anticipatory route selection, Transport Sci 38 (2004), 473–487.

[18]  J. Yang, P. Jaillet, and H. Mahmassani, Real-time multivehicle truckload pick-up and delivery problem, Transport Sci 38 (2004), 135–148.