Systems and Means of Informatics
2016, Volume 26, Issue 4, pp 114-123
ALGORITHMIC SOFTWARE OF THE OPTIMIZATION PROBLEM FOR CARGO DELIVERING BY WATER TRANSPORT
- E. M. Bronshtein
- I. E. Kopylov
Abstract
The paper considers the problem of constructing an optimal route of homogeneous cargo delivery from a family of producers to a family of consumers with the location of points on two riverbanks by a ship with limited capacity. Problems of this type arise, in particular, for the delivery of food and essential items to flood victims. The corresponding mathematical model is constructed. Several algorithms are suggested for solution of this problem (the exact algorithm of branch and bound, the greedy algorithm and two original heuristic algorithms that take into account the specific features of the problem). A computer experiment on simulated data was conducted using the developed software.
A comparative analysis of the efficiency of the algorithms was conducted by the experiment. Heuristic algorithms make it possible to solve the problem with the number of points equal to 50.
[+] References (14)
- Rubinstein, J. H., D. A. Thomas, and N. C. Wormald. 2001. A polynomial algorithm for a constrained traveling salesman problem. Networks 38:68-75.
- Cela, E., V. Deineko, and J. W. Gerhard. 2012. The x-and-y-axes travelling salesman problem. Eur. J. Oper. Res. 223:333-345.
- Cutler, M. 1980. Efficient special case algorithms for the N-line planar traveling salesman problem. Networks 10:183-195.
- Rote, G. 1992. The N-line traveling salesman problem. Networks 22:91-108.
- Deineko, V., R. Van Dal, and G. Rote. 1994. The convex-hull-and-line traveling salesman problem: A solvable case. Inform. Proc. Lett. 51:141-148.
- Deineko, V., and G. Woeginger. 1996. The convex-hull-and-line traveling salesman problem. Inform. Proc. Lett. 59:295-301.
- Bronshtein, E. M., and R.,V. Gindullin. 2011. Ob odnom klasse zadach marshruti- zatsii [On a class of routing problems]. Matematicheskoe modelirovanie [Mathematical Modeling] 23:123-122.
- Dantzig, G. B., and J. H. Ramser. 1959. The truck dispatching problem. Manag. Sci. 6:80-91.
- Gendreau, M., G. Laporte, and D. Vigo. 1999. Heuristics for the traveling salesman problem with pickup and delivery. Comput. Oper. Res. 26:699-714.
- Bronshtein, E. M., and I. E. Kopylov. 2015. Optimizatsionnayazadacha transportnoy logistiki s prostymi marshrutami peredvizheniya [An optimization problem of transport logistics with simple routes of movement]. Informatsionnye tekhnologii [Information Technology] 9:662-665.
- Bronshtein, E. M., andT. A. Zaiko. 2010. Determinirovannyeoptimizatsionnyezadachi transportnoy logistiki [Deterministic optimization of transport logistics tasks]. Av- tomatika i Telemekhanika [Automation and Remote Control] 10:133-147.
- Garey, M. R., and D. S. Johnson. 1979. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman. 338 p.
- Cormen, T.H., C.E. Leiserson, R. L. Rivest, and C. Stein. 2001. Introduction to algorithms. 2nd ed. MIT Press and McGraw-Hill. 1184 p.
- Sigal, I. Kh., and A. P. Ivanova. 2007. Vvedenie v prikladnoe diskretnoe programmi- rovanie: Modeli i vychislitel'nye algoritmy [An introduction to applied discrete programming: Models and computational algorithms]. Moscow: Fizmatlit. 304 p.
[+] About this article
Title
ALGORITHMIC SOFTWARE OF THE OPTIMIZATION PROBLEM FOR CARGO DELIVERING BY WATER TRANSPORT
Journal
Systems and Means of Informatics
Volume 26, Issue 4, pp 114-123
Cover Date
2016-11-30
DOI
10.14357/08696527160410
Print ISSN
0869-6527
Publisher
Institute of Informatics Problems, Russian Academy of Sciences
Additional Links
Key words
transportation logistics; optimization; heuristic methods; branch and bound method; greedy algorithm
Authors
E. M. Bronshtein  and I. E. Kopylov
Author Affiliations
Ufa State Aviation Technical University, 12 K. Marx Str., Ufa 450000, Russian Federation
|