Траектории сборщиков тележек у магазина

[e7e5]

Вам наверняка приходилось видеть, как на автомобильной стоянке у крупного магазина происходит сбор тележек, оставленных покупателями. Одну - к другой, и.т.д, потом один маленький "паровозик" едет к магазину.

Возник вопрос. Как собирать эти тележки, чтобы усилия по сбору минимизировать, а эффективность работы повысить? Вообще, как сборщики должны двигаться - по какой траектории, кривой?

Размер парковки порядка $100$ на $100$ м.

PS Если не хватает данных, то можно добавить.

[Бодигрим]

Если появление новых тележек не учитывается, то в первом приближении имеем задачу коммивояжера. Даже она, если я правильно помню, является NP-сложной.

[e7e5]

Бодигрим писал(а):

Если появление новых тележек не учитывается, то в первом приближении имеем задачу коммивояжера. Даже она, если я правильно помню, является NP-сложной.

Разобьем на две задачки:
1) Если дело идет к концу рабочего дня, то появление новых тележек можно не учитывать.
2) В другое время - тележки случаным образом появляются на парковке.

Куда же податься трудовому народу?
Да еще в "NP-сложной" задаче...

[Бодигрим]

Я сомневаюсь, что задача 2 окажется проще задачи 1. А о решении задачи коммивояжера написаны тонны и тонны статей: как точные алгоритмы, так и всяческие эвристики.

Кстати, я немного наврал: NP-сложность доказана в предположении общего случая. У нас же есть существенное ограничение на матрицу расстояний - она характеризует расположение объектов на плоскости в евклидовой метрике.

[e7e5]

Бодигрим писал(а):

Я сомневаюсь, что задача 2 окажется проще задачи 1. А о решении задачи коммивояжера написаны тонны и тонны статей: как точные алгоритмы, так и всяческие эвристики.

У нас же есть существенное ограничение на матрицу расстояний - она характеризует расположение объектов на плоскости в евклидовой метрике.

Тонны статей - замечательно. Но суть то? Как сборщику тележек собирать эти тележки?

[bubu gaga]

e7e5 писал(а):

Куда же податься трудовому народу?

Какова цель сборщика (objective) - меньше ходить, реже выходить, собирать только когда осталось слишком мало свободных тележек? Да и равномерность распределения как во времени так и по стоянке совершенно нереальное предположение.

[e7e5]

bubu gaga писал(а):

e7e5 писал(а):

Куда же податься трудовому народу?

Какова цель сборщика (objective) -

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

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

[bubu gaga]

e7e5 писал(а):

Эта подходящая цель?

Да нет конечно. Согласно этой цели надо иметь сборщиков столько же сколько и тележек и бежать за каждой как только она освободится. Путь минимальный, клиенты не ждут. Прежде чем что-то оптимировать подумайте что Вы хотите оптимировать. Уже по свойствам целевой функции можно думать как будет устроен алгоритм.

С другой стороны как экономист замечу, что есть более дешёвые способы решить проблему.