Просмотр исходного текста страницы Hardprob/Minimum Vehicle Scheduling On Tree

<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
* Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>, 
** на ребрах заданы времена проезда в 
*** прямом <em>f: E → N</em>
*** обратно направлении <em>b: E → N</em>
** на вершинах
*** время отгрузки-загрузки <em>r: V → N</em>
*** время обработки <em>h: V → N</em>

Найти расписание автомобильного объезда, которое 
* стартует в <em>v<sub>0</sub></em>, 
* посещает все вершины в <m>T</m>
* возвращается в <em>v<sub>0</sub></em>
* для любой вершины <m>v_{i}</m>
** обработка стартует не раньше <m>r(v_i)</m>.

Т.е. найти перестановку <m>\pi</m> вершин <m>1, \ldots, \vert V\vert</m>,  и функция ожидания <em>w</em>, такую что для любого <em>i</em>
<m>
 \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)})] ≥  r(v_{\pi(i)})
\end{displaymath}
</m>
где <em>d(u,v)</em> означает длину уникального пути из <em>u</em> в <em>v</em>.


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

<m>
d(v_0,v_{\pi(1)})+\sum_{j=1}^{n-1}[w(v_{\pi(j)})+h(v_{\pi(j)}) + 
d(v_{\pi(j)},v_{\pi(j+1)})] + w(v_{\pi(n)}) + h(v_{\pi(n)}) + d(v_{\pi(n)},v_0) → \min.
</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}}   -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
----
<small>
{{ViggoCode|node197}}
<!-- {{GDCode|}}  -->
<!-- * [ Задача в википедии]  -->
</small>
<!-- end -->

[[Категория:ClassicHardProblems]]