Теория Задачи Инструменты Социум Интересно

Личный Кабинет

Войдите или зарегистрируйтесь
Лаборатория LMatrix
Лаборатория Lmatrix занимается оптимизацией транспортных задач. Сюда можно отнести задачи поиска кратчайшего пути в ориентированных графах, применимые как к масштабам города и страны, классическую задачу обхода (коммивояжера), задачи оптимизации доставки грузов, задачи трехмерной упаковки.
Новости проекта

31.05.2013 - Универсиада. Маршрут по России и Татарстану. Официально и математически.

Огонь Универсиады приближается к финишу в Казани, но прежде пройдет по 43 городам республики Татарстан. Все об маршрутах огня в нашем анонсе.

Тематические статьи

26.07.2013 - Монитор в автомобиле будет дублировать экран смартфона

Водители смогут увидеть точную копию экрана своего смартфона на мониторе бортовой системы автомобиля. О сотрудничестве в этом направлении договорились разработчик ПО для удаленного управления устройствами RealVNC и производитель процессоров Texas Instruments.

29.03.2013 - Facebook на днях анонсирует собственный смартфон на Android

На следующей неделе Facebook собирается представить собственный смартфон с кастомизированной версией Android, утверждают источники. Ранее глава компании Марк Цукерберг опровергал слухи о выпуске собственного смартфона.

29.03.2013 - Основатель Facebook М.Цукерберг создает политическую организацию

Основатель социальной сети Facebook Марк Цукерберг создает политическую организацию, которая займется такими вопросами, как реформа образования, иммиграция и научные исследования, передает Associated Press со ссылкой на анонимный источник.

Vehicle routing problem

22 апреля 2011 года в 08:36   Просмотров: 5494

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. Proposed by Dantzig and Ramser in 1959, VRP is an important problem in the fields of transportation, distribution and logistics.[1] Often the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. Implicit is the goal of minimizing the cost of distributing the goods. Many methods have been developed for searching for good solutions to the problem, but for all but the smallest problems, finding global minimum for the cost function is computationally complex.

Overview

Several variations and specializations of the vehicle routing problem exist:
Vehicle Routing Problem with Pickup and Delivery (VRPPD): A number of goods need to be moved from certain pickup locations to other delivery locations. The goal is to find optimal routes for a fleet of vehicles to visit the pickup and drop-off locations.
Vehicle Routing Problem with LIFO: Similar to the VRPPD, except an additional restriction is placed on the loading of the vehicles: at any delivery location, the item being delivered must be the item most recently picked up. This scheme reduces the loading and unloading times at deliporarily unload items other than the ones that should be dropped off.
Vehicle Routing Problem with Time Windows (VRPTW): The delivery locations have time windows within which the deliveries (or visits) must be made.
Capacitated Vehicle Routing Problem (with or without Time Windows): CVRP or CVRPTW. The vehicles have limited carrying capacity of the goods that must be delivered.

Several software vendors have built software products to solve the various VRP problems. Numerous articles are available for more detail on their research and results.

Although VRP is related to the Job Shop Scheduling Problem, the two problems are typically solved using different techniques.[2]

References
^ Dantzig, G.B.; Ramser, J.H. (1959). "The Truck Dispatching Problem". Management Science 6 (1): 80–91. doi:10.1287/mnsc.6.1.80. ISSN 0025-1909. JSTOR 2627477.
^ Beck, J.C.; Prosser, P.; Selensky, E. (2003). "Vehicle routing and job shop scheduling: What’s the difference". Proceedings of the 13th International Conference on Artificial Intelligence Planning and Scheduling.

Further reading
Oliveira, H.C.B.de; Vasconcelos, G.C. (2008). "A hybrid search method for the vehicle routing problem with time windows". Annals of Operations Research. Retrieved 2009-01-29.
Frazzoli, E.; Bullo, F. (2004). "Decentralized algorithms for vehicle routing in a stochastic time-varying environment". Decision and Control, 2004. CDC. 43rd IEEE Conference on. 4.
Psaraftis, H.N. (1988). "Dynamic vehicle routing problems". Vehicle Routing: Methods and Studies 16: 223–248.
Bertsimas, D.J.; Van Ryzin, G. (1991). "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane". Operations Research 39 (4): 601–615. doi:10.1287/opre.39.4.601. JSTOR 171167.
Toth, P.; Vigo, D. (2001). The Vehicle Routing Problem. Philadelphia: Siam. ISBN 0898715792.

Оставить комментарий

Пожалуйста, введите символы, показанные на рисунке.

Примеры решений задачи коммивояжера (TSP)
design by lmatrix
О проекте | Написать письмо | Ссылки | Литература | Карта сайта