Задача по транспортной логистике - Страница 39

Ordinator · 26.03.2018, 14:18

На карте указать можешь, кто из них где?

квит · 26.03.2018, 14:51

на карте, которую я постил - лишь фрагмент данных.

в реальности их больше

квит · 26.03.2018, 15:00

сравнение этих задач по характеристикам

доставка питьевой воды
- от 3000 до 5000 точек в день
- относительно равномерное распределение точек по карте
- учет загрузки (в ТС влезает ограниченное кол-во груза - по объему и/или массе)
- временные окна разной ширины (могут быть от часа до 12 часов)
- время на обслуживание одного клиента от 2 до 10 мин
- изменения маршрута редки (например из-за отказа)

монтаж телекоммуникационных сетей
- от 200 до 400 заказов в день
- относительно равномерное распределение точек по карте, есть точки сгущения - новостройки
- учета загрузки нет (все необходимое оборудование и материалы обычно влазят в личный автомобиль монтажника)
- временные окна фиксированной ширины (2-3 часа)
- время на обслуживание одного клиента от 30 до 90 мин
- есть заказы день-в-день, т.е. возможность в режиме реального времени перестройки маршрута (добавление или удаление точек из маршрута)

Afa · 26.03.2018, 15:09

про воду. угадайка.
время - нафиг. интервалы ака тики. 10 минут - нормально. один тик на точку, расстояние пересчитать в тики, округление в плюс. добавление точки - пересчет всех маршрутов до всех остальных точек. и от. в фоне. в среднем при добавлении точки пересчитывается 3-5 к маршрутов. генератор и и оценку запихать в генетику и пусть крутится - субоптимальный вариант будет в наличии постоянно.

Afa · 26.03.2018, 15:22

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

квит · 26.03.2018, 15:31

Цитата:

Сообщение от Afa

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

ну мы примерно щас так и делаем, тока вместо генетического используем гибридный = случайный поиск + локальный перебор

квит · 26.03.2018, 15:46

Цитата:

Сообщение от Afa

время - нафиг. интервалы ака тики. 10 минут - нормально. один тик на точку, расстояние пересчитать в тики, округление в плюс.

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

Afa · 26.03.2018, 16:15

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

квит · 26.03.2018, 16:43

Цитата:

Сообщение от Afa

дата и время дофига ресурсов жрут на преобразования.

интересно, надо будет попробовать и сравнить )))

хотя у нас тоже не в формате дата-время хранится... уже сразу числом

но все равно интересно будет попробовать - у нас матрица расстояний есть, матрица доезда есть. будет матрица квантования )))

Afa · 26.03.2018, 16:59

ну я сравнивал. сначала думал свою парсилку ограниченную фигачить. и кусок математики. плюнул и внедрил тики. потом для унификации на юникстайм откатились - небольшой оверхид появился. но фиг с ним, не сильно критично уже было.
десятиминутные кста - массив тогда будет 144 тика на сутки. уже ни о чём. и не надо учитывать время на точке. есть тик - на точке успели.

26.03.2018, 14:51	#382
квит Администратор Регистрация: 18.02.2010 Сообщений: 17,007	на карте, которую я постил - лишь фрагмент данных. в реальности их больше __________________ Да здравствует то благодаря чему мы несмотря ни на что!!!

26.03.2018, 15:00	#383
квит Администратор Регистрация: 18.02.2010 Сообщений: 17,007	сравнение этих задач по характеристикам доставка питьевой воды - от 3000 до 5000 точек в день - относительно равномерное распределение точек по карте - учет загрузки (в ТС влезает ограниченное кол-во груза - по объему и/или массе) - временные окна разной ширины (могут быть от часа до 12 часов) - время на обслуживание одного клиента от 2 до 10 мин - изменения маршрута редки (например из-за отказа) монтаж телекоммуникационных сетей - от 200 до 400 заказов в день - относительно равномерное распределение точек по карте, есть точки сгущения - новостройки - учета загрузки нет (все необходимое оборудование и материалы обычно влазят в личный автомобиль монтажника) - временные окна фиксированной ширины (2-3 часа) - время на обслуживание одного клиента от 30 до 90 мин - есть заказы день-в-день, т.е. возможность в режиме реального времени перестройки маршрута (добавление или удаление точек из маршрута) __________________ Да здравствует то благодаря чему мы несмотря ни на что!!!

26.03.2018, 15:09	#384
Afa Шволочь. И провокатор. Регистрация: 12.02.2006 Сообщений: 31,295	про воду. угадайка. время - нафиг. интервалы ака тики. 10 минут - нормально. один тик на точку, расстояние пересчитать в тики, округление в плюс. добавление точки - пересчет всех маршрутов до всех остальных точек. и от. в фоне. в среднем при добавлении точки пересчитывается 3-5 к маршрутов. генератор и и оценку запихать в генетику и пусть крутится - субоптимальный вариант будет в наличии постоянно. __________________ ... Survivors will be shot again.

26.03.2018, 15:22	#385
Afa Шволочь. И провокатор. Регистрация: 12.02.2006 Сообщений: 31,295	про сетки. сходу таблицу приоритетов. приоритетней будет точка на минимальном расстоянии от предыдущей. отфильтрованная по интервалу, ага. и внести несколько стартовых точек. раскидав равномерно. начинать распределение с раздачи точек по бригадам без учёта времени пути по максимуму времени работы на точке. и выкидывать точки выпадающие за интервалы. попутно докидывая точки в окно при досрочном освобождении. наверно - мод генетики - с динамическим добавлением параметров. программизма раза в два больше, но график чуть не в онлайне держать возможно. да, субоптимум. да, все вариации задачки мерчанта - нафиг. сильно не катит. __________________ ... Survivors will be shot again.

26.03.2018, 16:15	#388
Afa Шволочь. И провокатор. Регистрация: 12.02.2006 Сообщений: 31,295	дата и время дофига ресурсов жрут на преобразования. не хочешь потом и кровью выстраданное в таймбазах - уходи на юникстайм. и внутри всё в нем, только вывод на клиенте преобразовывает. зачем - пересечения интервалов пересечением массивов очень дешево. __________________ ... Survivors will be shot again.

26.03.2018, 14:18	#381
Ordinator Солдат удачи Регистрация: 28.05.2011 Адрес: Пограничье Сообщений: 6,096	На карте указать можешь, кто из них где?

26.03.2018, 16:59	#390
Afa Шволочь. И провокатор. Регистрация: 12.02.2006 Сообщений: 31,295	ну я сравнивал. сначала думал свою парсилку ограниченную фигачить. и кусок математики. плюнул и внедрил тики. потом для унификации на юникстайм откатились - небольшой оверхид появился. но фиг с ним, не сильно критично уже было. десятиминутные кста - массив тогда будет 144 тика на сутки. уже ни о чём. и не надо учитывать время на точке. есть тик - на точке успели. __________________ ... Survivors will be shot again.