Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
bottleneck transportation; random transportation time; chance constraint; preference of routes; non-domination
bottleneck transportation; random transportation time; chance constraint; preference of routes; non-domination
Summary:
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.
References:
[1] Adeyefa, A. S., Luhandjula, M. K.: Multiobjective stochastic linear programming: an overview. Amer. J. Oper. Res. 1 (2011), 203-213. DOI 10.4236/ajor.2011.14023
[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 10.1137/0218065 | MR 1015267 | Zbl 0675.90029
[3] Branda, M., Dupačová, J.: Approximations and contamination bounds for probabilistic programs. Ann. Oper. Res. 193 (2012), 3-19. DOI 10.1007/s10479-010-0811-1 | MR 2874754
[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 10.1287/mnsc.1.1.49 | MR 0074103 | Zbl 0995.90512
[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 0056262 | Zbl 0045.09901
[7] Ford, L. R., Jr., Fulkerson, D. R.: Solving the transportation problem. Management Sci. 3 (1956), 24-32. DOI 10.1287/mnsc.3.1.24
[8] Garfinkel, R. S., Rao, M. R.: The bottleneck transportation problem. Naval Res. Logist. Quart. 18 (1971), 465-472. DOI 10.1002/nav.3800180404 | MR 0337282 | Zbl 0262.90040
[9] Ge, Y., Ishii, H.: Stochastic bottleneck transportation problem with flexible supply and demand quantity. Kybernetika 47 (2011), 4, 560-571. MR 2884861 | Zbl 1228.90136
[10] Geetha, S., Nair, K. P. K.: A stochastic bottleneck transportation problem. J. Oper. Res. Soc. 45 (1994), 583-588. Zbl 0807.90090
[11] Hammer, P. L.: Time minimizing transportation problem. Naval Res. Logist. Quart. 16 (1969), 345-357. MR 0260422
[12] Hitchcock, F. L.: The distribution of a product from several sources to numerous localities. J. Math. Phys. 20 (1941), 224-230. MR 0004469 | Zbl 0026.33904
[13] Kall, P., Wallace, S. W.: Stochastic Programming. John Wiley and Sons, New York 1994. MR 1315300 | Zbl 0812.90122
[14] Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Industr. Appl. Math. 5 (1957), 32-38. DOI 10.1137/0105003 | MR 0093429 | Zbl 0131.36604
[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 2052757 | Zbl 1042.90597
[16] Russell, R., Klingman, D., Partow-Navid, P.: An efficient approach to bottleneck transportation problem. Naval Res. Logist. Quart. 30 (1983), 13-35. DOI 10.1002/nav.3800300103 | MR 0709687
[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 10.1002/nav.3800190202 | MR 0321525
[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 10.1002/nav.3800230402 | MR 0446483
[19] Szwarc, W.: Some remarks on the time transportation problem. Naval Res. Logist. Quart. 18 (1971), 473-485. DOI 10.1002/nav.3800180405 | MR 0337298 | Zbl 0278.90046
Search
Partner of
