刘明艳，曾玲玲，李 群，柳艺娇，刘 芳

（1.长沙师范学院数学科学学院，湖南 长沙 410100；2.长沙师范学院图书馆，湖南 长沙 410100）

为了美化城市环境，减少城市空气中的飞尘，给人们提供一个优良的生活环境，在炎热干燥的天气为市区路面洒水是环卫洒水车的一项必不可少的工作。但是城市的街道纵横交错，路网复杂，如果不科学规划设计洒水车的行走路线，不但会造成公共资源的浪费，而且会加重本来就很辛苦的环卫工人的工作负担。因此，如何对环卫洒水车的行车路线科学规划、合理安排，不但是一个理论问题，而且是一个有用的实际问题。本文以长沙市长沙县星沙主城区为例，研究城市环卫洒水车最优行走路线模型。

1 问题的提出

长沙县星沙主城区的主要交通地图（来自百度）如图1所示，长沙县星沙主城区中有星沙大道、开元路、东升路、滨湖路、漓湘路等道路。

图1 星沙主城区街道地图

问题一：如何设计路线使得洒水车在最短时间内完成洒水任务？

问题二：如何设计路线使得洒水车完成所有道路洒水任务后恰好回到原点？

对问题一、问题二进行联合考虑，做出星沙主城区环卫洒水车最优行走路线模型。

2 问题分析

忽略道路网的形状、宽度，将其合理简化并转化为图论模型，道路抽象为边，交汇处抽象为点，道路长度为权，则图1 就可以转化图2。图2 中，将星沙大道、开元路、东升路、滨湖路、漓湘路、东四路、黄兴大道车流和人流密集以及路面灰尘大的道路转化为图论的边，将其的交汇点转化为点A、B、C、D、E、F、G、H、I、J、K、L。……