Модифицированная задача коммивояжёра

[Charlz_Klug]

Задача обстоит таким образом:
Имеется $n$ городов с сетью соединяющих их дорог. В каждом городе кроме первого города (база) имеется некоторое количество грузов $m$ разновидностей. Каждый груз из разновидностей обладает своей собственной неделимой массой $\{\alpha_1, \alpha_2, ..., \alpha_m\}$ тонн. Требуется за кратчайший путь свезти все грузы из этих городов на базу ($1$-й город) одной машиной. Грузоподъёмность машины равна $b$ тонн. То есть, машина выехала из $1$-го города объехала некоторое количество городов, набрала груза сколько могла и вернулась в город $1$. Разгрузилась и опять выехала собирать грузы и так до тех пор пока не свезла все грузы в первый город.

Как можно решить эту задачу? Я думаю что главным критерием будет продолжительность пути на тонну груза. Если взять грузоподъёмность равную бесконечности, то можно решить классическую задачу коммивояжёра, тогда разделив путь на общую массу можно получить идеальную для этой задачи удельную длину пути на $1$ тону. Больше ни до чего не додумался.

[Karan]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

[Mihaylo]

Для чего введены разновидности груза? Видимо подразумевается, что в кузов нельзя грузить груз разных видов... Почему не разбить тогда задачу на $m$ независимых?

[Charlz_Klug]

Mihaylo в сообщении #1164278 писал(а):

Для чего введены разновидности груза?

Смысл в том, что у каждой разновидности своя масса в тоннах. И можно было бы указывать что в городе $N$ три груза первой категории, один груз второй категории и шесть грузов двенадцатой категории.

Mihaylo в сообщении #1164278 писал(а):

Видимо подразумевается, что в кузов нельзя грузить груз разных видов...

В кузов можно грузить грузы разных разновидностей. Грузы не конфликтуют между собой.

Mihaylo в сообщении #1164278 писал(а):

Почему не разбить тогда задачу на $m$ независимых?

Рассмотрим такой случай:

Здесь $1 \text{---}$ база, куда нужно свезти грузы. В городе $2$ есть два груза: груз первой категории массой в $2$ тонны, груз второй категории массой в $1$ тонну. В городе $3$ есть только один груз первой категории массой в $2$ тонны. На середине отрезков указана длина пути. Грузоподъёмность машины равна $5$ тонн. Если машина просто объедет все города и заберёт грузы, то она проедет $8$ километров. Если машина отдельно будет собирать грузы первой категории, то она проедет $8$ километров, после чего она поедет за грузом второй категории и проделает путь в $6$ километров. Итого: $14$ километров. Очевидно, что проехать $8$ километров $\text{---}$ это лучше чем ехать $14$ километров.

[grizzly]

Charlz_Klug
Формулировка в данном виде действительно звучит противоестественно. Оттого и возникает желание включить телепатию. Более естественно было бы сказать, что в разных городах имеются грузоместа (заказы), которые нужно доставить на базу. И обозначить массу $j$-го грузоместа в пункте $A_m$ через $A_{m}^j,$ например. Такая постановка задачи по сути не отличается от Вашей, но в точности соответствует типичной задаче курьерской службы, которой нужно на РЦ (распределительный центр) доставить заказы от клиентов-отправителей.

Чем мотивирована Ваша задача? Просто желанием придумать хоть какое-нибудь обобщение транспортной? или практикой? или эта задача была Вам поставлена другими (учебник, преподаватель)?

[Charlz_Klug]

grizzly в сообщении #1164323 писал(а):

Более естественно было бы сказать, что в разных городах имеются грузоместа (заказы), которые нужно доставить на базу. И обозначить массу каждого грузоместа в пункте $A_m$ через $A_{m}^j,$ например. Такая постановка задачи по сути не отличается от Вашей, но в точности соответствует типичной задаче курьерской службы, которой нужно на РЦ (распределительный центр) доставить заказы от клиентов-отправителей.

Согласен.

grizzly в сообщении #1164323 писал(а):

Чем мотивирована Ваша задача?

Вообще говоря преподаватель дал задание написать курсовую. В курсовой нужно решить простую задачу либо о назначениях, либо о коммивояжёре, либо задачу о ранце. И написать программу для ЭВМ. Никаких изысков и дополнительных условий не требуется. Можете считать мой вопрос чисто праздным интересом. Найдётся ответ $\text{---}$ хорошо, не найдётся $\text{---}$ ну, тоже неплохо.

[mserg]

Кстати, на Kaggle есть близкие по теме задачи.

Развоз подарков от Санта Клауса с северного полюса:
https://www.kaggle.com/c/santas-stolen-sleigh
Если транспорт будет ездить задом наперед, то получится задача не развоза, а своза.
Kaggle интересен тем, что там есть данные, а также выкладывают готовые алгоритмы. И можно сравнивать свои достижения с результатами других людей.

Ну, и до кучи, коммивояжер:
https://www.kaggle.com/c/traveling-santa-problem