扫雪问题之最短时间

陈兴婉

一、问题重述

地图中实线表示马里兰州 （Maryland）威克米克市（Wicomico）清除积雪区域双行的道路，虚线是州高速公路。雪后，两辆扫雪车从地图*号标出的两点的每一地点以西约6.44（4mile）处出发清扫道路上的积雪。试为两车找出有效的路径。扫雪车可以通过高速公路进出市内道路。假定扫雪过程中车子不会损坏或停止，并且道路交叉处不需要附加扫雪程。

二、问题分析

要解决的问题是，为两台扫雪车设计出有效的路径进行威克米克市积雪道路的清扫工作。两辆扫雪车从地图*号标出的两点的每一地点以西约6.44km（4mile）处出发清扫道路上的积雪，市内的道路均为双向，扫雪车在道路的交叉点上可转向行驶。把道路的交点作为顶点集V，道路作为边集E，把所给地图定义为有向图,利用图论的知识进行分析，有向图D是强连通的，且每个顶点的入度等于出度，即有向图D是一个欧拉图，图中存在欧拉回路。

扫雪车遵守交通规则且靠右行驶，根据模型的假设，扫雪车经过路面一次就能把该单行道彻底地清扫干净，那么，扫雪车要完成任务就等于把所有的单向道路都至少行驶一遍。为了使扫雪车高效率地完成工作，考虑到两台扫雪车同时进行工作，根据模型假设，两扫雪车功率一样且作业过程以匀速进行，首先把地图分为南、北两个工作区，分别由两辆扫雪车负责。在两台车工作量相等情况下，设想其中一台扫雪车工作量减少一条道路，则另一台扫雪车的工作量将增加一条道路，即工作时间增长一个单位，使得工作效率下降。……