Коммивояжёр - или оптимизация пути.

@Only_HED · Регистрация: 28.05.2009

Студворк — интернет-сервис помощи студентам

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

К примеру у нас n машин и m заказов.

машина1
координаты машины Xi1j1
машина2
координаты машины Xi2j2
...

клиент 1
координаты подбора клиента Pi1j1 (pick)
координаты высадки клиента Di1j1 (drop)
Время подбора клиента T1

клиент 2
координаты подбора клиента Pi2j2 (pick)
координаты высадки клиента Di2j2 (drop)
Время подбора клиента T2

клиент 3
координаты подбора клиента Pi3j3 (pick)
координаты высадки клиента Di3j3 (drop)
Время подбора клиента T3

...

Варианты подбора по пути клиентов также учитывается, если он находиться в области выгодного подбора и дальнейшей высадки (т.е. небольшое отклонение от курса).

При появлении нового клиента, пересмотр уже готовых маршрутов.

Может стоить использовать Алгоритм флойда ?

@TanT · 14.07.2009, 17:20

какая скорость движения машин и начальные координаты? сколько клиентов можно по пути подобрать? в общем таксуют у нас нынше на чём? Ока или Лиазы

@Only_HED · 14.07.2009, 17:23 **[ТС]**

скорость движения машин и начальные координаты

Пускай скорость v = 1 начальные координаты (0,0)

сколько клиентов можно по пути подобрать?

3

@TanT · 14.07.2009, 18:04

(0,0) для всех машин? и время в пути для клиента должно быть минимально? и совсем забыл как у нас двигаются машины? то есть перемещение из точки (1,1) в точку (3,1) происходит за 3 единицы времени или square(4+1)

Добавлено через 13 минут 41 секунду
пардон, перемещение (1,1) в (3,2). в общем движение по рёбрам треугольника или по его диагонали

и ещё клиентов можно раньше подбирать или машина должна простаивать?

@Only_HED · 15.07.2009, 11:08 **[ТС]**

(0,0) для всех машин?

Вначале Да!

время в пути для клиента должно быть минимально?

Желательно, но Варианты подбора по пути клиентов немного может время увеличить

перемещение (1,1) в (3,2)

L = sqrt((1-3)^2 - (1-2)^2)) - его диагональ

Добавлено через 23 минуты 37 секунд

клиентов можно раньше подбирать или машина должна простаивать?

Желательно нагружать равномерно, но учитывая и расстояние (цену пути).

@TanT · 15.07.2009, 12:13

клиентов можно раньше подбирать или машина должна простаивать?
Желательно нагружать равномерно, но учитывая и расстояние (цену пути).

я не совсем об этом спрашивал, насколько важно и зачем в условии присутствует "Время подбора клиента T3"? что означает этот параметр?

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

@Only_HED · 15.07.2009, 12:21 **[ТС]**

зачем в условии присутствует "Время подбора клиента T3"?

Это когда я заказываю поездку на определенное время.

Т.е. нужно учитывать не только расстояние от высадки клиента к следующему, но и время во сколько забрать клиента.

@TanT · 15.07.2009, 17:35

В общем, фиксирую как я понял.
Начальные координаты машин (0,0). движение до клиента по прямой, соединяющей координаты подбора клиента Pi1j1 и координаты высадки клиента Di1j1, со скоростью 1.
Клиентов у которых есть параметр - Время подбора клиента T1 нужно подбирать в строго оговоренное время, ни раньше ни позже. Клиентов у которых этот параметр отсутсвует можно подбирать когда угодно.
Максимальная загрузка машины - 3 клиента. Время в пути не оговаривается, то есть можно возить довольно долго (хотя тут можно ввести ограничитель скажем не больше чем длительность поездки на 1,5 длины пути от Pi1j1 до Di1j1, так же надо продумать ограничение на "небольшие" отклонения от маршрута для подбора второго клиента)
Оптимальность проложения маршрутов как самособой разумеется.

Правильно понял?

P.S. Я это для чего пишу. Чётко сформулированная задача - это уже половина решения. А в код перевести это и кодер сможет.

@TanT · 16.07.2009, 21:14

черновой вариант. данные берёт из файла clients.txt, данные ввиде : time x_begin y_begin x_end y_end

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Only_HED 5 / 5 / 2 Регистрация: 28.05.2009 Сообщений: 29

	Коммивояжёр - или оптимизация пути. 14.07.2009, 17:03. Показов 1588. Ответов 8 Метки нет (Все метки) Задача заключается в том, чтобы оптимизировать пути движения транспорта от подбора клиента до его высадки. Распределение заказов по машинам. К примеру у нас n машин и m заказов. машина1 координаты машины Xi1j1 машина2 координаты машины Xi2j2 ... клиент 1 координаты подбора клиента Pi1j1 (pick) координаты высадки клиента Di1j1 (drop) Время подбора клиента T1 клиент 2 координаты подбора клиента Pi2j2 (pick) координаты высадки клиента Di2j2 (drop) Время подбора клиента T2 клиент 3 координаты подбора клиента Pi3j3 (pick) координаты высадки клиента Di3j3 (drop) Время подбора клиента T3 ... Варианты подбора по пути клиентов также учитывается, если он находиться в области выгодного подбора и дальнейшей высадки (т.е. небольшое отклонение от курса). При появлении нового клиента, пересмотр уже готовых маршрутов. Может стоить использовать Алгоритм флойда ? 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	14.07.2009, 17:20
	какая скорость движения машин и начальные координаты? сколько клиентов можно по пути подобрать? в общем таксуют у нас нынше на чём? Ока или Лиазы 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	14.07.2009, 18:04
	(0,0) для всех машин? и время в пути для клиента должно быть минимально? и совсем забыл как у нас двигаются машины? то есть перемещение из точки (1,1) в точку (3,1) происходит за 3 единицы времени или square(4+1) Добавлено через 13 минут 41 секунду пардон, перемещение (1,1) в (3,2). в общем движение по рёбрам треугольника или по его диагонали и ещё клиентов можно раньше подбирать или машина должна простаивать? 0

@TanT эволюционирую потихоньку 468 / 466 / 91 Регистрация: 30.06.2009 Сообщений: 1,401
	15.07.2009, 17:35
	В общем, фиксирую как я понял. Начальные координаты машин (0,0). движение до клиента по прямой, соединяющей координаты подбора клиента Pi1j1 и координаты высадки клиента Di1j1, со скоростью 1. Клиентов у которых есть параметр - Время подбора клиента T1 нужно подбирать в строго оговоренное время, ни раньше ни позже. Клиентов у которых этот параметр отсутсвует можно подбирать когда угодно. Максимальная загрузка машины - 3 клиента. Время в пути не оговаривается, то есть можно возить довольно долго (хотя тут можно ввести ограничитель скажем не больше чем длительность поездки на 1,5 длины пути от Pi1j1 до Di1j1, так же надо продумать ограничение на "небольшие" отклонения от маршрута для подбора второго клиента) Оптимальность проложения маршрутов как самособой разумеется. Правильно понял? P.S. Я это для чего пишу. Чётко сформулированная задача - это уже половина решения. А в код перевести это и кодер сможет. 0