组织循环运输问题的图论方法

A GRAPH—THEORETIC METHOD FOR SCHEDULING VEHICLE ROTING IN THE TRANSPORTATION PROBLEM

本文对组织循环运输路线问题,提出了一种图论方法。在一辆车作业的情况下,问题归结为求有向 Euler 图的有向 Euler 环游。对于多辆车作业的情况,问题转化为把有向 Euler 图分解为若干个边不重的有向子 Euler 环游的并。与此同时,也解决了车场的处理问题。

This paper prsents an algorithm for a special vehicle roting problem.In the case of one vehicle,the problem is transformed to be finding an Eulerian tour in a directed Euleriangraph. In the case of k vehicles,the problem is to decompose the Eulerian tour into k suptours.