Hardprob/Minimum Vehicle Scheduling On Tree — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена \geq на ≥)
Строка 18: Строка 18:
 
<m>
 
<m>
 
  \begin{displaymath}
 
  \begin{displaymath}
d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] \geq r(v_{\pi(i)})
+
d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] ≥  r(v_{\pi(i)})
 
\end{displaymath}
 
\end{displaymath}
 
</m>
 
</m>

Версия 11:29, 17 апреля 2023

  • Дерево с выделенным корнем ,
    • на ребрах заданы времена проезда в
      • прямом
      • обратно направлении
    • на вершинах
      • время отгрузки-загрузки
      • время обработки

Найти расписание автомобильного объезда, которое

  • стартует в ,
  • посещает все вершины в
  • возвращается в
  • для любой вершины
    • обработка стартует не раньше .

Т.е. найти перестановку вершин , и функция ожидания w, такую что для любого i где d(u,v) означает длину уникального пути из u в v.


Минимизировать полное время выполнения, т.е.


Задача в лаб22 (рид-онли просмотр)