| Title:
|
Chance constrained bottleneck transportation problem with preference of routes (English) |
| Author:
|
Ge, Yue |
| Author:
|
Chen, Minghao |
| Author:
|
Ishii, Hiroaki |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
5 |
| Year:
|
2012 |
| Pages:
|
958-967 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
bottleneck transportation |
| Keyword:
|
random transportation time |
| Keyword:
|
chance constraint |
| Keyword:
|
preference of routes |
| Keyword:
|
non-domination |
| MSC:
|
68Q25 |
| MSC:
|
90C15 |
| MSC:
|
90C35 |
| MSC:
|
90C70 |
| idMR:
|
MR3086862 |
| . |
| Date available:
|
2012-12-17T13:36:32Z |
| Last updated:
|
2013-09-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143092 |
| . |
| Reference:
|
[1] Adeyefa, A. S., Luhandjula, M. K.: Multiobjective stochastic linear programming: an overview..Amer. J. Oper. Res. 1 (2011), 203-213. 10.4236/ajor.2011.14023 |
| Reference:
|
[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. Zbl 0675.90029, MR 1015267, 10.1137/0218065 |
| Reference:
|
[3] Branda, M., Dupačová, J.: Approximations and contamination bounds for probabilistic programs..Ann. Oper. Res. 193 (2012), 3-19. MR 2874754, 10.1007/s10479-010-0811-1 |
| Reference:
|
[4] Charnes, A., Cooper, W. W.: The stepping stone method of explaining linear programming calculations in transportation problems..Management Sci. 1 (1954), 49-69. Zbl 0995.90512, MR 0074103, 10.1287/mnsc.1.1.49 |
| Reference:
|
[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. |
| Reference:
|
[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. Zbl 0045.09901, MR 0056262 |
| Reference:
|
[7] Ford, L. R., Jr., Fulkerson, D. R.: Solving the transportation problem..Management Sci. 3 (1956), 24-32. 10.1287/mnsc.3.1.24 |
| Reference:
|
[8] Garfinkel, R. S., Rao, M. R.: The bottleneck transportation problem..Naval Res. Logist. Quart. 18 (1971), 465-472. Zbl 0262.90040, MR 0337282, 10.1002/nav.3800180404 |
| Reference:
|
[9] Ge, Y., Ishii, H.: Stochastic bottleneck transportation problem with flexible supply and demand quantity..Kybernetika 47 (2011), 4, 560-571. Zbl 1228.90136, MR 2884861 |
| Reference:
|
[10] Geetha, S., Nair, K. P. K.: A stochastic bottleneck transportation problem..J. Oper. Res. Soc. 45 (1994), 583-588. Zbl 0807.90090 |
| Reference:
|
[11] Hammer, P. L.: Time minimizing transportation problem..Naval Res. Logist. Quart. 16 (1969), 345-357. MR 0260422 |
| Reference:
|
[12] Hitchcock, F. L.: The distribution of a product from several sources to numerous localities..J. Math. Phys. 20 (1941), 224-230. Zbl 0026.33904, MR 0004469 |
| Reference:
|
[13] Kall, P., Wallace, S. W.: Stochastic Programming..John Wiley and Sons, New York 1994. Zbl 0812.90122, MR 1315300 |
| Reference:
|
[14] Munkres, J.: Algorithms for the assignment and transportation problems..J. Soc. Industr. Appl. Math. 5 (1957), 32-38. Zbl 0131.36604, MR 0093429, 10.1137/0105003 |
| Reference:
|
[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. Zbl 1042.90597, MR 2052757 |
| Reference:
|
[16] Russell, R., Klingman, D., Partow-Navid, P.: An efficient approach to bottleneck transportation problem..Naval Res. Logist. Quart. 30 (1983), 13-35. MR 0709687, 10.1002/nav.3800300103 |
| Reference:
|
[17] Srinivasan, V., Thompson, G. L.: An operator theory of parametric programming for the transportation - I..Naval Res. Logist. Quart. 19 (1972), 205-226. MR 0321525, 10.1002/nav.3800190202 |
| Reference:
|
[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. MR 0446483, 10.1002/nav.3800230402 |
| Reference:
|
[19] Szwarc, W.: Some remarks on the time transportation problem..Naval Res. Logist. Quart. 18 (1971), 473-485. Zbl 0278.90046, MR 0337298, 10.1002/nav.3800180405 |
| . |
