21.4. The definition of a complex transport task
Let’s describe the complex transport task with the help of the following –
 .
V ={v1, …, vn} – the variety of point for acceptance and dispatching of the goods. For each point the following information is given vi = vi (toi,m, tii,m, ai,t), where toi,m = toi,m (tn, tk, p), tii,m = tii,m (tn, tk, p), such information represents the goods to be collected and dispatched. Therefore, each goods tn have the following characteristic number of packing tk and the level of urgency (priority) p(0,1). ai,t is the variety of vehicle which currently locates at this point.
A={a1, …, ak} – stands for the variety of vehicles where each element characterizes the ability of the vehicle aj = aj (xj, sj, abj). The index xj contains the information about the cargo allowed to be transported, working load and the volume of the vehicle storage space. sj is the cost of passage of 1 km distance, besides, the load level is taken to consideration: empty vehicle, half volume, full load, not available (during the execution of the route, or at the repair station), abj – the index, which shows the necessity of the vehicle return to the starting point after the completion of the route.
T = {t1, …, tm} – characteristics of goods which are to be transported. tp = tp (tn, tm, tv, tt), where tn – designation (code), tm – weight of the packing, tv – volume of the packing , tt – type of goods.
C = (ci1,i2) – the cost of time-independent goods transportation from point i1 to point i2. Thus the cost of transportation comprises the cost of time-independent goods transportation multiplied by the cost of the vehicle transfer.
R = {r1, …, rs} – vehicle routes, где ri = {0,…,vc,…,vl,…,0} – sequence of points passage.
In this model the definition of VRP task shall be changed as follows.
According to the requirement concerning the changes of the goods content, it’s essential to meet the requirements of the itinerary points with priority degree which is over some value P* during particular period of time under condition of minimization of the total transportation cost due to development of vehicle routes.
The target function of the task is the development of such routes R which will ensure minimum cost of the itinerary points passage, so that  , therefore the delivery of goods with priority level higher than P* is ensured.
It should be mentioned that when p* takes its minimal value within the spectrum of positive value of p, the task will appear to be enlarged transport task which can meet the requirements of all itinerary points.
22.5. Conclusion
Within the environment of constant increase of cargo flow the solution of transport routing task and transport task in its classical representation is quite important nowadays. During previous 50 years a lot of methods aimed at solving of such kind of tasks have been developed. Nevertheless the problem of enterprises which deals with transport logistics remain as acute as it used to be before. This situation can be explained by the fact that the classical definition of the task very often cannot be applied in real life because it does not take to account a lot of peculiarities of the real working conditions of the companies, which every day face the challenge concerning the development of optimal way to satisfy the needs of the customers.
This article presents the analysis of requirements of the companies, and it provides the task definition which meet the most up-to-date needs of the transportation companies, and which takes to account physical aspects of their work, business procedures of the enterprise and also all the limitations prescribed by the legislation and other factors which influence the activity of the companies working within this domain.
Список литературы
B.D. Backer, P. Kilby, P. Prosser, P. Shaw, Solving vehicle routing problems using constraint programming and metaheuristics, Journal of Heuristics 6 (4): 501–525, 2000.
Barbarosoglu G. A tabu search algorithm for the vehicle routing problem // Computers & Operations Research. – 1999. – № 26. – p. 255–270.
Bean J.C. Genetic algorithms and random keys for sequencing and optimization // ORSA Journal on Computing. – 1994. – № 6. – P. 154-160.
D. Sterratt, B. Graham, A. Gillies, D. Willshaw. Principles computational modeling in neuroscience // Cambridge University Press, the Edinburgh Building, Cambridge CB2 8RU, UK, 404, 2011, 404 p.
David Kriesel. A Brief Introduction to Neural Networks // monograph, http://www.dkriesel.com, 2005, 266 p.
G. Clarke, J.W. Wright. Scheduling of vehicles from a central depot to a number of delivery points // Operations Research, 12: 568-581, 1964.
George B. Dantzig. Decomposition Principle for Linear Programs. Operations Research 8: 101–111, 1960.
Gilbert Laporte. The Vehicle Routing Problem: An overview of exact and approximate algorithms. // European Journal of Operational Research 59 (1992) 345-358.
Hoong Chuin Lau, Melvyn Sim, Kwong Meng Teo. Vehicle routing problem with time windows and a limited number of vehicles. // European Journal of Operational Research 148 (2003) 559–569.
Johnson D. S., McGeoch L. A. The Traveling Salesman Problem: A Case Study in Local Optimization. Local Search in Combinatorial Optimization / Aarts E. H. L., Lenstra J. K. (eds.). N. Y.: John Willey & Sons, 1995.
Osman I.H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem // Ann. Oper. Res. 1993. Vol. 41.
P. Toth, D. Vigo. The vehicle routing problem. SIAM monographs on discrete mathematics and applications, Philadelphia, USA, 2002
S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani. Algorithms // monograph, 2006, 318 p.
Villani, C. Optimal Transport, Old and New. Book manuscript, 2006.
Xu J. A network flow-based tabu search heuristic for the vehicle routing problem / J. Xu, J.P. Kelly // Transportation Science. – 1996. – № 30. – P. 379–393.
The VRP Web // Internet source – http://neo.lcc.uma.es/vrp/
Словарь
Adaptive resonance theory (ART) – теория адаптивного резонанса
Artificial intelligence – искусственный интеллект
Artificial neural nets – искусственные нейронные сети
Axon – аксон
Backpropagation of error learning – метод обратного распространения ошибки
Bias neuron – нейрон смещения
Bin Packing Problem (BPP) – задача об упаковки рюкзака
Binary threshold function – двоичная пороговая функция
Brainstem – ствол головного мозга
Cargo capacity – грузоподъемность
Cargo redistribution task – задача распределения грузов
Central nervous system (CNS) – центральная нервная система
Cerebellum – мозжечок
Cerebral cortex – кора головного мозга
Cerebrum (telencephalon) – головной мозг
Chemical synapse – химический синапс
Circular routes – замкнутые (кольцевые) маршруты
Concentration gradient – градиент концентрации
Data entity - объект данных
Data medium - носитель данных
Data set - набор данных
Data Warehouse (DW) - информационное хранилище
Declarative language - непроцедурный язык
Dendrite – дендрит
Direct recurrence (self-recurrence) – прямая рекурсия
Directed graph – ориентированный граф
Electrical Gradient – электрический градиент
Electrical synapse – электрический синапс
Fermi function – функция Ферми
Genome – геном
Hinton diagram – хинтон схема
Human circadian rhythm – циркадный ритм человека
Hyperbolic tangent – гиперболический тангенс
Hypothalamus – гипотоламус
Idetifier – идентификатор
Index - индекс
Intelligent house - интеллектуальный дом
Interbrain (diencephalon) – промежуточный мозг
Intergrated - интегрированный
Irrational number - иррациональное число
Logistic function – логическая функция
Matrix of transportation costs – матрица стоимостей передвижения
Membrane – мембрана
Membrane potential – мембранный потенциал
Multi product transportation task – мультипродуктовая транспортная задача
Multilayer perceptrons – многослойные персептроны
Multimodal transportation services – мультимодальные перевозки
Neural Network – нейронная сеть
Neuron – нейрон
Neurotransmitter – медиатор
Number normalized form - нормализованная форма числа
Object - объект
Object-Oriented database (OODB) - Объектно-Ориентированная База Данных (ООБД)
One task mode - однозадачный режим
Output function – функция выхода
Peripheral nervous system (PNS) – периферийная нервная система
Potassium – калий
Recurrence – рекурсия
Self-organizing feature maps (SOM) – самоорганизующиеся карты
Sodium – натрий
Synaps – синапс
Transport flow – транспортный поток
Transportation matrix – матрица транспортировки
Transportation routing – транспортная задача
Traveling Salesman Problem (TSP) – задача коммивояжера
Undirected graph – неориентированный граф
Vehicle Routing Problem (VRP) – задача маршрутизации транспорта
Weight matrix – матрица весов
|
