Несколько транспортных средств без емкости и стоимостной матрицы

Question

Я пытаюсь создать VRP с использованием двух транспортных средств одного типа и начать с того же места. Я хочу, чтобы решение создало маршрут для каждого транспортного средства в проблеме наиболее экономичным способом. Я использую GraphHopper для расчета расстояний и времени на дороге между каждым местоположением службы и создания матрицы транспортных расходов с этой информацией.

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

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

Я что-то упустил?

Могу поместить образцы кода, если потребуется.

Спасибо!

Answer 1

Без ограничений по пропускной способности всегда будет оптимальным использование одного транспортного средства (если выполняется неравенство треугольника, которое для дорожных расстояний). Другими словами, VRP без ограничений пропускной способности = TSP.

Подумайте об этом следующим образом: предположим, что у вас есть два маршрута: один заканчивается в городе A (до возвращения в депо), а другой начинается в городе B (после выхода из склада). Теперь представьте, что вы удаляете ногу от A до депо и ногу от депо до B и добавляете ногу от A до B. По неравенству треугольника c_AB < = c_A, depot + C_depot, B, поэтому новое решение дешевле, чем Старый.