Kybernetika 48 no. 5, 958-967, 2012

Chance constrained bottleneck transportation problem with preference of routes

Yue Ge, Minghao Chen and Hiroaki Ishii


This paper considers a variant of the bottleneck transportation problem. For each supply-demand point pair, the transportation time is an independent random variable. Preference of each route is attached. Our model has two criteria, namely: minimize the transportation time target subject to a chance constraint and maximize the minimal preference among the used routes. Since usually a transportation pattern optimizing two objectives simultaneously does not exist, we define non-domination in this setting and propose an efficient algorithm to find some non-dominated transportation patterns. We then show the time complexity of the proposed algorithm. Finally, a numerical example is presented to illustrate how our algorithm works.


bottleneck transportation, random transportation time, chance constraint, preference of routes, non-domination


90C35, 90C15, 90C70, 68Q25


  1. A. S. Adeyefa and M. K. Luhandjula: Multiobjective stochastic linear programming: an overview. Amer. J. Oper. Res. 1 (2011), 203-213.   CrossRef
  2. R. K. Ahuja, J. B. Orlin and R. E. Tarjan: Improved time bounds for the maximum flow problem. SIAM J. Comput. 18 (1989), 939-954.   CrossRef
  3. M. Branda and J. Dupačová: Approximations and contamination bounds for probabilistic programs. Ann. Oper. Res. 193 (2012), 3-19.   CrossRef
  4. A. Charnes and W. W. Cooper: The stepping stone method of explaining linear programming calculations in transportation problems. Management Sci. 1 (1954), 49-69.   CrossRef
  5. M. H. Chen, H. Ishii and C. X. Wu: Transportation problems on a fuzzy network. Internat. J. Innov. Comput. Inform. Control 4 (2008), 1105-1109.   CrossRef
  6. G. B. Dantzig: Application of the simplex method to a transportation problem. In: Activity Analysis of Production and Allocation, Chapter 23, Cowles Commission Monograph 13. Wiley, New York 1951.   CrossRef
  7. L. R. Ford, Jr. and D. R. Fulkerson: Solving the transportation problem. Management Sci. 3 (1956), 24-32.   CrossRef
  8. R. S. Garfinkel and M. R. Rao: The bottleneck transportation problem. Naval Res. Logist. Quart. 18 (1971), 465-472.   CrossRef
  9. Y. Ge and H. Ishii: Stochastic bottleneck transportation problem with flexible supply and demand quantity. Kybernetika 47 (2011), 4, 560-571.   CrossRef
  10. S. Geetha and K. P. K. Nair: A stochastic bottleneck transportation problem. J. Oper. Res. Soc. 45 (1994), 583-588.   CrossRef
  11. P. L. Hammer: Time minimizing transportation problem. Naval Res. Logist. Quart. 16 (1969), 345-357.   CrossRef
  12. F. L. Hitchcock: The distribution of a product from several sources to numerous localities. J. Math. Phys. 20 (1941), 224-230.   CrossRef
  13. P. Kall and S. W. Wallace: Stochastic Programming. John Wiley and Sons, New York 1994.   CrossRef
  14. J. Munkres: Algorithms for the assignment and transportation problems. J. Soc. Industr. Appl. Math. 5 (1957), 32-38.   CrossRef
  15. A. Prékopa: Probabilistic programming. In: Stochastic Programming (A. Ruszczynski and A. Shapiro, eds.), Handbook in Operations Research and Management Science 10 (2003), Elsevier, Amsterdam, pp. 267-352.   CrossRef
  16. R. Russell, D. Klingman and P. Partow-Navid: An efficient approach to bottleneck transportation problem. Naval Res. Logist. Quart. 30 (1983), 13-35.   CrossRef
  17. V. Srinivasan and G. L. Thompson: An operator theory of parametric programming for the transportation - I. Naval Res. Logist. Quart. 19 (1972), 205-226.   CrossRef
  18. V. Srinivasan and G. L. Thompson: Algorithm for minimizing total cost, bottleneck time and bottleneck shipment in transportation problems. Naval Res. Logist. Quart. 23 (1976), 567-595.   CrossRef
  19. W. Szwarc: Some remarks on the time transportation problem. Naval Res. Logist. Quart. 18 (1971), 473-485.   CrossRef