Geodesic
Chance constrained bottleneck transportation problem with preference of routes
Kybernetika, Tome 48 (2012) no. 5, pp. 958-967 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 68Q25, 90C15, 90C35, 90C70
Keywords: bottleneck transportation; random transportation time; chance constraint; preference of routes; non-domination 
@article{KYB_2012_48_5_a8,
     author = {Ge, Yue and Chen, Minghao and Ishii, Hiroaki},
     title = {Chance constrained bottleneck transportation problem with preference of routes},
     journal = {Kybernetika},
     pages = {958--967},
     year = {2012},
     volume = {48},
     number = {5},
     mrnumber = {3086862},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a8/}
}
TY  - JOUR
AU  - Ge, Yue
AU  - Chen, Minghao
AU  - Ishii, Hiroaki
TI  - Chance constrained bottleneck transportation problem with preference of routes
JO  - Kybernetika
PY  - 2012
SP  - 958
EP  - 967
VL  - 48
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a8/
LA  - en
ID  - KYB_2012_48_5_a8
ER  - 
%0 Journal Article
%A Ge, Yue
%A Chen, Minghao
%A Ishii, Hiroaki
%T Chance constrained bottleneck transportation problem with preference of routes
%J Kybernetika
%D 2012
%P 958-967
%V 48
%N 5
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a8/
%G en
%F KYB_2012_48_5_a8
Ge, Yue; Chen, Minghao; Ishii, Hiroaki. Chance constrained bottleneck transportation problem with preference of routes. Kybernetika, Tome 48 (2012) no. 5, pp. 958-967. http://geodesic.mathdoc.fr/item/KYB_2012_48_5_a8/

[1] Adeyefa, A. S., Luhandjula, M. K.: Multiobjective stochastic linear programming: an overview. Amer. J. Oper. Res. 1 (2011), 203-213. | DOI

[2] Ahuja, R. K., Orlin, J. B., Tarjan, R. E.: Improved time bounds for the maximum flow problem. SIAM J. Comput. 18 (1989), 939-954. | DOI | MR | Zbl

[3] Branda, M., Dupačová, J.: Approximations and contamination bounds for probabilistic programs. Ann. Oper. Res. 193 (2012), 3-19. | DOI | MR

[4] Charnes, A., Cooper, W. W.: The stepping stone method of explaining linear programming calculations in transportation problems. Management Sci. 1 (1954), 49-69. | DOI | MR | Zbl

[5] Chen, M. H., Ishii, H., Wu, C. X.: Transportation problems on a fuzzy network. Internat. J. Innov. Comput. Inform. Control 4 (2008), 1105-1109.

[6] Dantzig, G. B.: 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. | MR | Zbl

[7] Ford, L. R., Jr., Fulkerson, D. R.: Solving the transportation problem. Management Sci. 3 (1956), 24-32. | DOI

[8] Garfinkel, R. S., Rao, M. R.: The bottleneck transportation problem. Naval Res. Logist. Quart. 18 (1971), 465-472. | DOI | MR | Zbl

[9] Ge, Y., Ishii, H.: Stochastic bottleneck transportation problem with flexible supply and demand quantity. Kybernetika 47 (2011), 4, 560-571. | MR | Zbl

[10] Geetha, S., Nair, K. P. K.: A stochastic bottleneck transportation problem. J. Oper. Res. Soc. 45 (1994), 583-588. | Zbl

[11] Hammer, P. L.: Time minimizing transportation problem. Naval Res. Logist. Quart. 16 (1969), 345-357. | MR

[12] Hitchcock, F. L.: The distribution of a product from several sources to numerous localities. J. Math. Phys. 20 (1941), 224-230. | MR | Zbl

[13] Kall, P., Wallace, S. W.: Stochastic Programming. John Wiley and Sons, New York 1994. | MR | Zbl

[14] Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Industr. Appl. Math. 5 (1957), 32-38. | DOI | MR | Zbl

[15] Prékopa, A.: 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. | MR | Zbl

[16] Russell, R., Klingman, D., Partow-Navid, P.: An efficient approach to bottleneck transportation problem. Naval Res. Logist. Quart. 30 (1983), 13-35. | DOI | MR

[17] Srinivasan, V., Thompson, G. L.: An operator theory of parametric programming for the transportation - I. Naval Res. Logist. Quart. 19 (1972), 205-226. | DOI | MR

[18] Srinivasan, V., Thompson, G. L.: Algorithm for minimizing total cost, bottleneck time and bottleneck shipment in transportation problems. Naval Res. Logist. Quart. 23 (1976), 567-595. | DOI | MR

[19] Szwarc, W.: Some remarks on the time transportation problem. Naval Res. Logist. Quart. 18 (1971), 473-485. | DOI | MR | Zbl