2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

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

 
 
 
 
Сообщение21.09.2008, 21:43 
Бодигрим писал(а):
Если появление новых тележек не учитывается, то в первом приближении имеем задачу коммивояжера. Даже она, если я правильно помню, является NP-сложной.

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

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

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

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

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

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

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

 
 
 
 
Сообщение22.09.2008, 20:20 
Аватара пользователя
e7e5 писал(а):
Куда же податься трудовому народу?


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

 
 
 
 
Сообщение22.09.2008, 20:39 
bubu gaga писал(а):
e7e5 писал(а):
Куда же податься трудовому народу?


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

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

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

 
 
 
 
Сообщение22.09.2008, 22:04 
Аватара пользователя
e7e5 писал(а):
Эта подходящая цель?


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

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

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group