Vehicle Routing Problem: Overview of Models, Methods and Algorithms. Part 1

Rate this item
(0 votes)

MAGAZINE  №4 (93) August 2019

AUTHORS 

Valeyev R.S.

Valeyeva A.F.

Goncharova Y.A. - Cand.of Tech.Sc., Software engineer, Research and Production Center «GeoTek» (Ufa, Russia)

CATEGORY Analytics and reviews Optimization and mathematical modelling

 

ABSTRACT

The paper reviews well-known routing problems (Vehicle Routing Problem, VRP), that are an essential part of the transport logistics. The mathematical models of various routing problems’ classes are given: with account to a transport vehicle’s carrying capacity (TV); with the time windows; with split delivery; with a given planning time horizon (periodic problem); with backhauls; with satellite facilities. Since the routing problems are the NP-hard objectives of combinatorial optimization, for the sake of their practical application in the sphere of the transportation management the various heuristic algorithms are being developed. The known metaheuristics are expounded in the paper that present the local search algorithms as well as constructive algorithms, namely, the genetic algorithm; the evolutionary strategies; the ant colony algorithms’ series; the alternating neighbourhood search algorithm. Herewith, the attention is paid to the solution coding and to some neighbourhood constructing solution operations. Since in practice the routing problems are closely connected with the goods disposition within the transport vehicles (the 3D packing problem), the approximate algorithms which provide obtaining the goods packing map are described. The given review of various routing problems’ classes and the effective methods of their solution aid in practical problems of the effective routes search for the goods delivery to various customers. So, Part 2 of the paper describes the mathematical model and the methods of one practical task resolving that is processed together with the 3D packing problem of goods inside car transport vehicles.

 Electronic version

 Keywords:  

Read 78 times

Contacts

Postal address:

125 319  Chernуakhovskogo str.16

phone/fax (495) 771 32 58

Working with authors: Levina Tamara Vladimirovna

mob. 8-962-965-48-54

E-mail: levina-tamara@mail.ru

ISSN 2587-6775

Published since 2004

Journal's Indexing