Обговорення користувача:Olenka77

Застосування

Дана задача має місце за умов, коли фактичний попит кожного споживача стає відомим в останній момент перед відправкою вантажу.

Розв'язок задачі

Розглянемо цю задачу в умовах обмежень на тривалість маршруту.

Така задача визначена на направленій графа G=(V₀,A), де V₀ = {0}∪V, 0 представляє базу, а V={1,…,N} — множину споживачів, A={(i, j) | i, j ∈ V₀, i ≠j} — множина дуг графи. Із кожною дугою (i, j) графа асоціюється з часом руху по цій дузі t_ij та вартисть її проходження c_ij . Ємність транспортного засобу позначимо через Q.

Індивідуальні попити споживачів є незалежними рівномірно розподіленими цілочисловими випадковими величинами з відомим розподілом і представлені з допомогою вектора . Для бази матимемо: d(0) = d(0) =${\overline {d}}$ (0) = 0.

Нехай T_k = {c_lk ,…, c_mk } — маршрут k-го транспортного засобу, а L(T_k) — загальний час необхідний для його проходження. Нехай$\varphi$(T_k, P, d) — додатковий час проходження маршуруту на здійснення рекурсивних дій при стратегії P і реалізації попиту d ∈ D. В такому разі очікувана тривалість проходження маршруту рівна:

L_E (T_k , P) = L(T_k) + E( $\varphi$, P, d)),.

де E($\varphi$(T_k, P, d)) — очікуване значення додаткового часу подорожі для проходження маршруту T_k для рекурсівної стратегії P та реалізації попиту d ∈ D.

Введемо також наступні позначення: C(T_k) — загальні затраті на проходження маршруту T_k , <φ(T_k, P, d) — загальні додаткові затраті на здійснення рекурсивних дій при стратегії P і реалізації попиту d ∈ D. Тоді матимемо:

C_E (T_k, P) = C(T_k) + E(φ(T_k, P, d)).

В такому разі задачу можна представити у наступному виді:

$\min _{Tk}$$\sum _{k}LE(Tk,P)$$\min _{Tk}$$\sum _{k}CE(Tk,P)$

L_E (T_k , P)≤ R

де R — максимальна допустима тривалість маршруту.

Розглянемо її розв'язання з допомогою генетичних алгоритмів.

Нехай маємо множину U всіх можливих маршрутів, що містить m елементів. В такому рази початковою популяцією вважатимемо множину із m випадково згенерованих кортежів {x_ij }, елементи яких (гени) можна інтерпретувати наступним чином:

X_ij =${\Bigg \{}$ 1, якщо i – й маршрут використовується

0, інакше

Для кожного елемента початкової популяції обчислюємо значення фітнес-функції, яка виражатиме в числовому виді те, наскільки цей елемент відповідає умовам оптимальності.

Подальші ітерації генетичного алгоритму полягатимуть в наступному:

1. Елементи популяції сортуються в порядку погіршення значення фітнес-функції.
2. Генерується наступна популяція:

• В кожну наступну популяцію потрапляє частина елементів попередньої популяції із найкращими значеннями фітнес-функції;
• Із попередньої популяції створюються пари батьків, із яких із допомогою крос-оверу генеруються елементи наступної популяції;
• Частина елементів нової популяції зазнають мутації.

Умовами для завершення генетичного алгоритму може бути виконання наперед заданої кількості ітерацій або те, що значення фітнес-функції збіглося до певного значення. Після завершення роботи алгоритму розв'язком задачі вважається елемент вихідної популяції із найкращим значенням фітнес-функції.

Основною перевагою застосування генетичних алгоритмів до розв'язання задачі маршрутизації транспортних засобів в умовах стохастичного попиту є відсутність чітких вимог до фітнес-функції, що зумовлює їх високу гнучкість до врахування різноманітних додаткових умов та обмежень, що накладаються на розв'язок задачі, як кількісних, так і якісних.

Джерела

1. L. Bianchi, M. Birattari, M. Manfrin, M.Mastrolilli, L. Paquete, O. Rosi-Doria, and T. Schiavinotto. Metaheuristics for the vehicle routing problem with stochastic demands/ In Pro- ceedings of the 8th international conference on Parallel Problem Solving from Nature (PPSN VIII), — Springer LNCS 3242, 2004.
2. Eiben, Agoston E. Introduction to evolutionary programming/ A.E.Eiben,J.E.Smith, — Springer-Verlag Berlin Heidelberg, 2003
3. Novoa, Clara M., The Real-Time Vehicle Routing Problem with Stochastic Demands (VRPSD), — Research Enhancement Program Final Reports. Paper 95, 2006- http://ecommons.txstate.edu/osp_regs/95

Зображення

Дякуємо за завантаження нових зображень! На жаль, при автоматичній перевірці їх описів виявились деякі проблеми. Зверніть увагу, що опис кожного зображення обов'язково повинен містити вказівку на його автора і шаблон ліцензії. Докладніше про правильний опис зображень ви можете прочитати на сторінках ВП:ЛЗ, ВП:ЛЗ-КД, ВП:ШАП, ВП:ДК. Зображення, що не мають необхідних даних в описах, підлягають безумовному вилученню через 7 днів після виявлення. Будь ласка, виправте описи наступних зображень (зробити це можна, натиснувши посилання «редагувати» вгорі сторінки зображення):

• Файл:Лінійна функція належності.png: Ліцензія без шаблону

• Файл:Формула 2.png: Ліцензія без шаблону

--BunykBot (обговорення) 15:09, 30 листопада 2012 (UTC)