The Dynamic Assignment Problem

References

• Ahuja R., Magnanti T., Orlin J.Network Flows: Theory, Algorithms and Applications (1992) (Prentice Hall, Upper Saddle River, NJ) Google Scholar
• Balinski M. Signature methods for the assignment problem. Oper. Res. (1985) 33:527–537Link, Google Scholar
• Balinski M. A competitive (dual) simplex method for the assignment problem. Math. Programming (1986) 34(2):125–141Crossref, Google Scholar
• Balinski M., Gomory R. A primal method for the assignment and transportation problems. Management Sci. (1964) 10:578–593Link, Google Scholar
• Bander J., White C. C. Markov decision processes with noise-corrupted and delayed state observations. J. Oper. Res. Soc. (1999) 50(6):660–668Crossref, Google Scholar
• Barr R., Glover F., Klingman D. The alternating path basis algorithm for assignment problems. Math. Programming (1977) 13:1–13Crossref, Google Scholar
• Bean J., Birge J., Smith R. Aggregation in dynamic programming. Oper. Res. (1987) 35:215–220Link, Google Scholar
• Bertsekas D. A new algorithm for the assignment problem. Math. Programming (1981) 21:152–171Crossref, Google Scholar
• Bertsekas D. The auction algorithm: A distributed relaxation method for the assignment problem. Ann. Oper. Res. (1988) 14:105–123Crossref, Google Scholar
• Bertsekas D., Castanon D. Adaptive aggregation methods for infinite horizon dynamic programming. IEEE Trans. Automatic Control (1989) 34(6):589–598Crossref, Google Scholar
• Bertsekas D., Tsitsiklis J.Neuro-Dynamic Programming (1996) (Athena Scientific, Belmont, MA) Google Scholar
• Bertsekas D., Tsitsiklis J., Wu C. Rollout algorithms for combinatorial optimization. J. Heuristics (1997) 3(3):245–262Crossref, Google Scholar
• Birge J. Decomposition and partitioning techniques for multistage stochastic linear programs. Oper. Res. (1985) 33(5):989–1007Link, Google Scholar
• Birge J., Louveaux F.Introduction to Stochastic Programming (1997) (Springer-Verlag, New York) Google Scholar
• Chen Z.-L., Powell W. A convergent cutting-plane and partial-sampling algorithm for multistage linear programs with recourse. J. Optimization Theory Appl. (1999) 103(3):497–524Crossref, Google Scholar
• Cheung R. K.-M., Powell W. B. SHAPE: A stochastic hybrid approximation procedure for two-stage stochastic programs. Oper. Res. (2000) 48(1):73–79Link, Google Scholar
• Cook T., Russell R. A simulation and statistical analysis of stochastic vehicle routing with timing constraints. Decision Sci. (1978) 9:673–687Crossref, Google Scholar
• Dantzig G.Linear Programming and Extensions (1963) (Princeton University Press, Princeton, NJ) Crossref, Google Scholar
• Gale D., Shapley L. College admissions and the stability of marriage. Amer. Math. Monthly (1962) 69:9–15Crossref, Google Scholar
• Gendreau M., Guertin F., Potvin J., Taillard E. Parallel tabu search for real-time vehicle routing and dispatching. Transportation Sci. (1999) 33:381–390Link, Google Scholar
• Glasserman P., Yao D.Monotone Structure in Discrete-Event Systems (1994) (John Wiley and Sons, New York) 234–238Google Scholar
• Godfrey G., Powell W. B. An adaptive, dynamic programming algorithm for stochastic resource allocation problems, I: Single period travel times. Transportation Sci. (2002) 36(1):21–39Link, Google Scholar
• Goldfarb D. Efficient dual simplex methods for the assignment problem. Math. Programming (1985) 33:187–203Crossref, Google Scholar
• Gross O. The bottleneck assignment problem. (1959) . Technical Report p-1630. The RAND CorporationGoogle Scholar
• Hall L., Schulz A., Shmoys D., Wein L. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 22:513–544Link, Google Scholar
• Higle J., Sen S. Stochastic decomposition: An algorithm for two stage linear programs with recourse. Math. Oper. Res. (1991) 16(3):650–669Link, Google Scholar
• Hinderer K. On approximate solutions of finite-stage dynamic programs. Dynamic Programming and Its Applications (1978) (Academic Press, New York) Google Scholar
• Hoogeveen J., Vestjens A. A best possible deterministic on-line algorithm for minimizing delivery time on a single machine. SIAM J. Discrete Math. (2000) 13:56–63Crossref, Google Scholar
• Hung M. A polynomial simplex method for the assignment problem. Oper. Res. (1983) 31:595–600Link, Google Scholar
• Infanger G.Planning under Uncertainty: Solving Large-scale Stochastic Linear Programs (1994) (Scientific Press Series, Boyd & Fraser, New York) Google Scholar
• Jonker R., Volegnant A. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing (1987) 38:325–340Crossref, Google Scholar
• Kall P., Wallace S.Stochastic Programming (1994) (John Wiley and Sons, New York) Google Scholar
• Lageweg B., Lenstra J., Kan A. R., Stougie L. Stochastic integer programming by dynamic programming. Numerical Techniques for Stochastic Optimization (1988) (Springer-Verlag, Berlin, Germany) 403–412Crossref, Google Scholar
• Laporte G., Louveaux F. The integer l-shaped method for stochastic integer programs with complete recourse. Oper. Res. Lett. (1993) 13(3):133–142Crossref, Google Scholar
• Ling B., Butler R. Comparing effects of aggregation methods on statistical and spatial properties of simulated spatial data. Photogrammatic Engrg. Remote Sensing (1999) 65(1):73–84Google Scholar
• Louveaux F., van der Vlerk M. Stochastic programming with simple integer recourse. Math. Programming (1993) 61:301–325Crossref, Google Scholar
• Mendelssohn R. An iterative aggregation procedure for Markov decision processes. Oper. Res. (1982) 30(1):62–73Link, Google Scholar
• Morin T. L. Computational advances in dynamic programming. Dynamic Programming and Its Applications (1978) (Academic Press, New York) Google Scholar
• Murty K.Network Programming (1992) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Pinedo M.Scheduling: Theory Algorithms, and Systems (1995) (Prentice Hall, Englewood Cliffs, NJ) Google Scholar
• Powell W. B. A review of sensitivity results for linear networks and a new approximation to reduce the effects of degeneracy. Transportation Sci. (1989) 23(4):231–243Link, Google Scholar
• Powell W. B. A stochastic formulation of the dynamic assignment problem with an application to truckload motor carriers. Transportation Sci. (1996) 30(3):195–219Link, Google Scholar
• Powell W., Snow W., Cheung R. Adaptive labeling algorithms for the dynamic assignment problem. Transportation Sci. (2000a) 34:67–85Link, Google Scholar
• Powell W., Towns M. T., Marar A. On the value of globally optimal solutions for dynamic routing and scheduling problems. Transportation Sci. (2000b) 34(1):50–66Link, Google Scholar
• Psaraftis H. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Sci. (1980) 14:130–154Link, Google Scholar
• Psaraftis H. Dynamic vehicle routing problems. Vehicle Routing: Methods and Studies (1988) (North Holland, Amsterdam, The Netherlands)223–248Google Scholar
• Psaraftis H. Dynamic vehicle routing: Status and prospects. Ann. Oper. Res. (1995) 61:143–164Crossref, Google Scholar
• Puterman M. L.Markov Decision Processes (1994) (John Wiley and Sons, New York) Crossref, Google Scholar
• Regan A., Mahmassani H. S., Jaillet P. Evaluation of dynamic fleet management systems—Simulation framework. Transportation Res. Record (1998) 1648:176–184Crossref, Google Scholar
• Rogers D., Plante R., Wong R., Evans J. Aggregation and disaggregation techniques and methodology in optimization. Oper. Res. (1991) 39(4):553–582Link, Google Scholar
• Secomandi N. A rollout policy for the vehicle routing problem with stochastic demands. Oper. Res. (2001) 49(5):796–802Link, Google Scholar
• Shapley L. S. Complements and substitutes in the optimal assignment problem. Naval Res. Logist. Quart. (1962) 9:45–48Crossref, Google Scholar
• Shmoys D. B., Wein J., Williamson D. P. Scheduling parallel machines online. SIAM J. Comput. (1995) 24(6):1313–1331Crossref, Google Scholar
• Sutton R., Barto A.Reinforcement Learning (1998) (MIT Press, Cambridge, MA) Google Scholar
• Swihart M., Papastravrou J. D. A stochastic and dynamic model for the single-vehicle pickup and delivery problem. Eur. J. Oper. Res. (1999) 114(3):447–464Crossref, Google Scholar
• Tomizawa N. On some techniques useful for solution of transportation network problems. Networks (1972) 1:179–194Google Scholar
• Tsitsiklis J., Van Roy B. An analysis of temporal-difference learning with function approximation. IEEE Trans. Automatic Control (1997) 42:674–690Crossref, Google Scholar
• Van Slyke R., Wets R. L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. (1969) 17(4):638–663Crossref, Google Scholar
• Whitt W. Approximations of dynamic programs I. Math. Oper. Res. (1978) 3:231–243Link, Google Scholar
• Whitt W. Approximations of dynamic programs II. Math. Oper. Res. (1979) 4:179–185Link, Google Scholar
• Wilson L. Assignment using choice lists. Oper. Res. Quart. (1977) 28(3):569–578Crossref, Google Scholar