Завданнях маршрутизації автотранспорту
Основна проблема capacitated автомобіль маршрутизації (CVRP) складається з безлічі клієнтів поставки здійснюються автопарком на базі центрального складу. Подорожі відстані між кожною парою клієнтів, а також і з депо, як відомо, кожен предмет поставки має відоме кількість, і кожен автомобіль має фіксовану потужність. Метою завдання полягає в мінімізації загальною протяжністю обумовлений транспортних засобів, задовольняючи всі замовлення клієнтів. Подальші цілі проблема також може розглядатися, як мінімізувати розмір флоту або балансу безлічі маршрутів транспортних засобів, щоб зробити їх рівними в довжині, як це можливо.
Проблема була вперше представлена на Данциг і Рамсер (1959), і він отримав велику увагу, так як. Огляд роботи в VRSP можна знайти в книгах золотий і Асад (1988), Той і Віго (2001) і, зовсім недавно, Золотий, Reghavan і Василь (2008). VRSP класифікується як NP-важка задача, яка має на увазі, що при збільшенні розміру завдання, розрахунок часу, необхідного, щоб знайти оптимальне рішення для будь-якого відомого методу збільшується в геометричній прогресії. Оптимальне рішення може бути знайдене за проблеми обмеженого розміру, проте для того, щоб знайти оптимальне рішення непрактично обсяг обчислень зусиль може знадобитися, щоб знецінити все неоптимальні маршрути. На практиці евристичні методи звичайно застосовуються. Евристика не гарантує, щоб знайти оптимальне рішення, однак, добре продумана евристичний знайдете хорошої якості рішень в розумні терміни розрахунків.
Є багато комерційних програмних пакетів для забезпечення рішень в реальному світі VRSPs. Такі пакети пропонують значні переваги в порівнянні з будь-яким ручним способом за допомогою евристики. Постачальники програмного забезпечення прагнуть пропагувати значні суми грошей, що такий підхід може врятувати. Тим не менше, більшість з них тільки з максимальної економії коштів, які, як правило, досягається за рахунок мінімізації загальної вартості подорожі вимірюється від відстані або часу, необхідного і звести до мінімуму розмір флоту. Такі поліпшення, неминуче будуть скоротити викиди виробництва автомобілів, проте в даний час не прагнуть звести до мінімуму вплив на навколишнє середовище безпосередньо. OR / MS сьогодні регулярно публікує огляди доступних пакетів. У самий останнє дослідження лише одного постачальника програмного забезпечення підкреслив вплив на навколишнє середовище в якості майбутнього функція / турботу про своїх програмних пакетів (OR / MS сьогодні, 2008).
Основні CVRP була введена в попередньому розділі, однак через проблеми з маршрутизацією рідко так просто на практиці. Наприклад, додаткові обмеження, які можуть зробити істотний вплив на діяльність включає в себе правові вимоги на водіння і робочого часу, а також той факт, що деякі клієнти вимагають доставки зокрема транспортних засобів (для вантаження і розвантаження причин). У даному розділі представлені деякі більш проблеми особливостей, які можуть виникнути на практиці, а деякі дослідження в результаті моделей.
Дуже часто, коли йде обмеження поставки можуть бути зроблені. Тимчасове вікно для поставки визначається початок і кінець часу. В залежності від аналізованої завдання, часовий інтервал можна розглядати або як тверді або м'які обмеження. Жорстких обмежень вимагає, щоб транспортний засіб повинен чекати до тих пір вікна починається, перш ніж приймати пологи або не мають прибути до того часу, вікно починає. Після тимчасового вікна завершує поставки не можуть бути зроблені. М'якого дозволяє доставки виробляється за межами тимчасового вікна на страту вартості. Ця вартість може бути або фіксованою ціною або може бути пропорційна скоростиглість або запізнення поставки. Алгоритми, щоб знайти точне рішення проблеми з жорстким вікна час були розроблені Kolen, Кан і Trienekens (1987) і Kallehauge, Ларсен і Медсен (2006). Евристичні методи були використані Bräysy (2002), а останнім часом Лау, Сим і Тео (2003) і Фу, Eglese і Лі (2008), які розглядаються як тверді і м'які вікна часу.
Проблеми, які дозволяють включати backhauls замовників, яким потрібна пункт збору і доставлений в депо. Це на додаток до клієнтів очікують поставок (також відомий як linehauls). Це загальне, що будь-які поставки здійснюються до backhauls вважаються. Підходи дає точні вирішення проблеми обмежених розмірів були розроблені, наприклад, Той і Віго (1997) або Mingozzi, Георгій і Балдаччі (1999). Евристичні методи також застосовуються до проблеми см. Дюамель, Potvin і Руссо (1997), Брандао (2006) і Тавакколі-Могаддам, Saremi і Ziaee (2006).