Минимизируйте максимальное расстояние между транспортными средствами - PullRequest
Новая
       33

Минимизируйте максимальное расстояние между транспортными средствами

0 голосов
/ 06 июля 2018

Рекомендуется использовать коэффициент стоимости пролета, чтобы минимизировать максимальное расстояние между транспортными средствами 

# Try to minimize the max distance among vehicles.
# /!\ It doesn't mean the standard deviation is minimized
distance_dimension.SetGlobalSpanCostCoefficient(100)

взято из https://developers.google.com/optimization/routing/vrp#example

Это особенно полезно, когда функция стоимости основана не на расстоянии (т. Е. Расходе топлива), а на времени в пути, и цель состоит в том, чтобы последний автомобиль вернулся в депо как можно раньше.

Q1: можно ли определить целевую функцию как максимальную стоимость среди транспортных средств (не сумму общих затрат и глобальный промежуток)?

Если это невозможно, мне интересно, в чем причина. Я мог бы предположить, что это A) трудно реализовать такое ограничение или B) я упускаю некоторые неявные недостатки, которые приводят к плохим решениям (по сравнению с использованием ограничения span).

Я заметил, что ограничение глобального диапазона, даже если я установлю его на 1000 (но что это вообще значит?), Не гарантирует даже то, что используются все транспортные средства. Конечно, я могу улучшить это решение, используя больше транспортных средств, верно?

EDIT: Вот минимальный рабочий пример. 5 автомобилей доступны для обслуживания 20 остановок. Я определяю равномерное время в пути 1 час между остановками, поэтому оптимальное решение состоит в том, что каждый маршрут состоит из 4 остановок, и все машины возвращаются в депо через 4 часа. Без глобального ограничения пролета один автомобиль выполняет всю работу с общим временем 20 часов. При глобальном ограничении пролета (коэффициент = 1000) два транспортных средства обслуживают 10 остановок каждый. 

import ortools.constraint_solver.pywrapcp
import ortools.constraint_solver.routing_enums_pb2

stops = 20
vehicles = 5
depot = 0

routing = ortools.constraint_solver.pywrapcp.RoutingModel(stops, vehicles, depot)

def cost_function(x,y):
    return 1

routing.SetArcCostEvaluatorOfAllVehicles(cost_function)

evaluator = cost_function
slack_max = 24
capacity = 24
fix_start_cumul_to_zero = True
name = "time"
routing.AddDimension(evaluator, slack_max, capacity, fix_start_cumul_to_zero, name)

time_dimension = routing.GetDimensionOrDie("time")
time_dimension.SetGlobalSpanCostCoefficient(1000)

search_params = ortools.constraint_solver.pywrapcp.RoutingModel.DefaultSearchParameters()
assignment = routing.SolveWithParameters(search_params)

Вывод решения на плоттер:

Маршрут для автомобиля 0: 0 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 0 Продолжительность маршрута 0: 10 ч

Маршрут для автомобиля 1: 0 -> 10 -> 0 Продолжительность маршрута 1: 2 ч

Маршрут для транспортного средства 2: 0 -> 0 Продолжительность маршрута 2: 1 ч

Маршрут для транспортного средства 3: 0 -> 0 Продолжительность маршрута 3: 1 ч

Маршрут для транспортного средства 4: 0 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 Продолжительность маршрута 4: 10 ч

Общая продолжительность всех маршрутов: 24 ч

...