基于图论模型的快递员最优投递路线设计

时文俊

摘 要：随着网络的普及，“网购”的流行，导致快递员派送快件的工作量增大。本文根据快递员投递快件的实际问题建立图论模型，利用图论中求欧拉回路的算法，为快递员设计最优投递路线，从而节约快递员的工作时间，减少其劳动强度，提高劳动效率。

关键词：欧拉图；欧拉回路；权数

图论是以图为研究对象的数学分支，近年来发展迅速，应用非常广泛. 它已经广泛地应用在物理学、化学、控制论、信息科学、科学管理、电子计算机等各个领域. 在实际生活、生产和科学研究中，有很多问题都可以用图论的理论和方法来解决。

随着网络的普及，“网上购物”成为时下比较流行的一种购物方式，它有着价格比实体店优惠、购物不受时间限制、方便、快捷的优点，还可以送过货上门，足不出户就能买到所需要的物品. 网上购物的流行，促使了快递行业的快速发展，“快递”成了妇孺皆知的词语了，但这也无疑加大了快递员的工作量. 本文根据实际问题建立图论模型，利用图论的理论和方法设计合理的投递路线，以减少快递员的工作时间和劳动强度，提高其劳动效率。

一、图论概念介绍

定义1. 1称数学结构■为一有向图，其中V（G）是非空集合，■是从集合E（G）到V（G）×V（G）的一个映射。称V（G）和E（G）分别为图G的顶点集合和边集合，■为G的关联函数. 若■，则简写成e=uv，称u是有向边e的尾，v为有向边e的头。 若图G为无向图，e=uv时，称顶点u与v是边e的端点。 若■，称e1与e2是重边。

定义1. 2在顶边交错链■中，■■■且■，则称W是图G的一条道路，其中允许vi=vj或ei=ej，i≠j，称Vo是W的起点，Vk是W的终点，K为路长，■称为W的内点。 各边相异的道路称为行迹，各顶相异的道路称为轨道，记成P（Vo，Vk），起点与终点重合的道路称为回路，起点与终点重合的轨道叫圈，长K的圈称为K阶圈；u，v两顶的距离是指u与v为起止点的最短轨道的长度，记成d（u，v），若存在道路以u，v为起止顶，则称u与v在图G中连通，G中任二顶皆连通时，称G为连通图。

定义1. 3 设G是连通的无向图，在图G中包含一切边的行迹叫做欧拉行迹，包含一切边的闭行迹叫做欧拉回路。若G中存在欧拉回路，则称G为欧拉图。

定理1. 1连通图G是欧拉图的充分必要条件是对任意的V∈V（G），d（v）是偶数，其中d（v）表示v的次数，即与v相关联的边数。

定义1. 4图G中的桥是指G中的一边e∈E（G），使得G-e的连通分支数增加。

二、模型的建立

这个问题的实际模型为：快递员从快递公司选好快件去投递，然后返回快递公司，他必须经过由他负责投递的每条街道至少一次，为这位快递员设计一条投递线路，使其行走的路程最短，耗时最少。

该问题的图论模型为：把快递员所负责的投递区域看成一个加权的连通图G，其顶点为街道的交叉口，边为每条街道，权为每条街道的长度（正数）。快递员的最优投递路线即为求G的一个包含一切边（至少一次）的回路W，使这条回路W的总权数最小. 若对G中对每条边e∈E（G），用一非负实数w（e）表示其权，求G的包含一切边的回路W，使得W的总权数■。

三、问题的解决

1.快递员负责的投递区域对应的街道图是欧拉图若快递员负责的投递区域对应的街道图G是欧拉图，根据定义1. 3，G中必含有欧拉回路，即包含G的一切边的闭行迹. 那么所求的最优投递路线就是G的一条欧拉回路。

根据定理1. 1，如果某快递员所负责的投递区域的街道图中没有奇顶点（顶点的次数是奇数），那么他就可以从快递公司出发，经过每个街道一次，且仅一次，最后回到快递公司。

尽管由定理1. 1可以很轻松地判定给定的街道图是否为欧拉图，但如果沿着一条随意的路线走，也是无法找到欧拉回路的. 假如街道图如图1，如果按照图中箭头所示的方向从顶点V6出发走了3步以后，就无法再进行下去了。其失败的原因是用了V6V5边之后，在未用过的边的导出子图中V5V7是桥，提前过桥的后果是断了去左侧的5-圈的后路。

因此，非必要时，不要通过未用过的边的导出子图的桥，根据这一思路，1921年，Fleury设计了一个求欧拉回路的有效算法，简记为FE算法：

（1）任取■，令Wo=Vo，

（2）设路■已选定，则从E（G）-E（W）中选一条边ei+1，使得ei+1与vi相关联，且非必要时，ei+1不要选G-E（W）的桥。

（3）反复执行（2），直至每边皆入选为止。

FE算法是有效算法，其时间复杂度为■

用FE算法在图1中可选得一条符合条件的最优路，即欧拉回路：■。但符合条件的欧拉回路并不唯一，■也是满足条件的一条欧拉回路。

2.快递员负责的投递区域对应的街道图是非欧拉图

因为所对应的街道图是非欧拉图，而快递员要从快递公司出发，他必须经过由他负责投递的每条街道至少一次，并回到快递公司，因此有些街道要走不止一次。重复走某条街道相当于在街道图中为该街道添加一条重边。问题转化为在图中添加一些重边，构造成一个欧拉图并且要求添加的重边的权数之和最小。

把一个非欧拉图通过添加重边变成欧拉图，也就是通过添加重边把图中每个顶点的度数均变为偶数。因此，在添加重边时，很明显应该选择某个奇度顶点为端点添加重边，如果重边的另一端点也是奇度顶点，那么这条重边将这两个奇度顶点均变为偶度顶点；如果重边的另一端点是偶度顶点，则添加重边后，还必须从偶度顶点出发再添加一条重边与其他一个奇度顶点相连，因为原来的偶度顶点又变成了奇度顶点。

添加重边时还要注意两个原则：（1）不能重复添加重边，重复的重边应成对去掉，这样并不改变每一个顶点的奇偶性；（2）每一个圈上添加的重边的总长不能超过圈长的一半，否则应将此圈上添加的重边去掉，改在此圈上原来没有添加重边的路线上添加重边，这样也不改变每一个顶点的奇偶性。

以上两个原则既保证了添加重边后每个顶点都是偶度顶点，又保证了添加重边的总长最短。因此，添加重边后的街道图必存在欧拉回路。根据FE算法，即可找到满足条件的最优线路。下面看一具体的例子。

假设某快递公司的某快递员负责的投递范围为郑州市二七区的中原路以南、陇海路以北、大学路以西、嵩山路以东的范围. 以街道的交叉口为顶点，街道为边，街道的长度（单位：百米）为权数建立一个加权图，如图2所示。

在这个图中，街道的交叉点共有16个，但三次点有12个，因此要想构造出欧拉图，需要添加的重边至少有6条。根据添加重边的原则，每一个圈上添加的重边的总长不能超过圈长的一半，根据街道图的特点，图中包含的圈比较多，但很明显，大圈之中包含着小圈，故只要每个小圈中添加的重边的权数不超过圈长的一半，那么在大圈中必然也满足添加重边的权数不超过圈长的一半。因此，我们容易得到图3、图4两种添加重边的方案，

图3的方案是从N 点出发增加3条重边，最终将街道图的每个顶点均为偶度顶点，图4的方案是添加重边IJ ，把顶点J 变成了奇度顶点，再添加重边JK 将J，K 均变为偶度顶点。根据各边的权数大小，可知这两种方案添加的重边的权数之和是相等的，也是最小的。 假设快递公司在N 点，从图3、图4中，可分别找到一条欧拉回路：

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

快递员沿着这两条路线派送快件，即是最优路线。 由于FE算法中，欧拉回路不唯一，所以快递员派送快件的最优路线也不唯一。

参考文献：

[1]王树禾.图论[M].北京：科学出版社，2009.

[2]王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京：北京大学出版社，2011.

[3]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2010.endprint

摘 要：随着网络的普及，“网购”的流行，导致快递员派送快件的工作量增大。本文根据快递员投递快件的实际问题建立图论模型，利用图论中求欧拉回路的算法，为快递员设计最优投递路线，从而节约快递员的工作时间，减少其劳动强度，提高劳动效率。

关键词：欧拉图；欧拉回路；权数

图论是以图为研究对象的数学分支，近年来发展迅速，应用非常广泛. 它已经广泛地应用在物理学、化学、控制论、信息科学、科学管理、电子计算机等各个领域. 在实际生活、生产和科学研究中，有很多问题都可以用图论的理论和方法来解决。

随着网络的普及，“网上购物”成为时下比较流行的一种购物方式，它有着价格比实体店优惠、购物不受时间限制、方便、快捷的优点，还可以送过货上门，足不出户就能买到所需要的物品. 网上购物的流行，促使了快递行业的快速发展，“快递”成了妇孺皆知的词语了，但这也无疑加大了快递员的工作量. 本文根据实际问题建立图论模型，利用图论的理论和方法设计合理的投递路线，以减少快递员的工作时间和劳动强度，提高其劳动效率。

一、图论概念介绍

定义1. 1称数学结构■为一有向图，其中V（G）是非空集合，■是从集合E（G）到V（G）×V（G）的一个映射。称V（G）和E（G）分别为图G的顶点集合和边集合，■为G的关联函数. 若■，则简写成e=uv，称u是有向边e的尾，v为有向边e的头。 若图G为无向图，e=uv时，称顶点u与v是边e的端点。 若■，称e1与e2是重边。

定义1. 2在顶边交错链■中，■■■且■，则称W是图G的一条道路，其中允许vi=vj或ei=ej，i≠j，称Vo是W的起点，Vk是W的终点，K为路长，■称为W的内点。 各边相异的道路称为行迹，各顶相异的道路称为轨道，记成P（Vo，Vk），起点与终点重合的道路称为回路，起点与终点重合的轨道叫圈，长K的圈称为K阶圈；u，v两顶的距离是指u与v为起止点的最短轨道的长度，记成d（u，v），若存在道路以u，v为起止顶，则称u与v在图G中连通，G中任二顶皆连通时，称G为连通图。

定义1. 3 设G是连通的无向图，在图G中包含一切边的行迹叫做欧拉行迹，包含一切边的闭行迹叫做欧拉回路。若G中存在欧拉回路，则称G为欧拉图。

定理1. 1连通图G是欧拉图的充分必要条件是对任意的V∈V（G），d（v）是偶数，其中d（v）表示v的次数，即与v相关联的边数。

定义1. 4图G中的桥是指G中的一边e∈E（G），使得G-e的连通分支数增加。

二、模型的建立

这个问题的实际模型为：快递员从快递公司选好快件去投递，然后返回快递公司，他必须经过由他负责投递的每条街道至少一次，为这位快递员设计一条投递线路，使其行走的路程最短，耗时最少。

该问题的图论模型为：把快递员所负责的投递区域看成一个加权的连通图G，其顶点为街道的交叉口，边为每条街道，权为每条街道的长度（正数）。快递员的最优投递路线即为求G的一个包含一切边（至少一次）的回路W，使这条回路W的总权数最小. 若对G中对每条边e∈E（G），用一非负实数w（e）表示其权，求G的包含一切边的回路W，使得W的总权数■。

三、问题的解决

1.快递员负责的投递区域对应的街道图是欧拉图若快递员负责的投递区域对应的街道图G是欧拉图，根据定义1. 3，G中必含有欧拉回路，即包含G的一切边的闭行迹. 那么所求的最优投递路线就是G的一条欧拉回路。

根据定理1. 1，如果某快递员所负责的投递区域的街道图中没有奇顶点（顶点的次数是奇数），那么他就可以从快递公司出发，经过每个街道一次，且仅一次，最后回到快递公司。

尽管由定理1. 1可以很轻松地判定给定的街道图是否为欧拉图，但如果沿着一条随意的路线走，也是无法找到欧拉回路的. 假如街道图如图1，如果按照图中箭头所示的方向从顶点V6出发走了3步以后，就无法再进行下去了。其失败的原因是用了V6V5边之后，在未用过的边的导出子图中V5V7是桥，提前过桥的后果是断了去左侧的5-圈的后路。

因此，非必要时，不要通过未用过的边的导出子图的桥，根据这一思路，1921年，Fleury设计了一个求欧拉回路的有效算法，简记为FE算法：

（1）任取■，令Wo=Vo，

（2）设路■已选定，则从E（G）-E（W）中选一条边ei+1，使得ei+1与vi相关联，且非必要时，ei+1不要选G-E（W）的桥。

（3）反复执行（2），直至每边皆入选为止。

FE算法是有效算法，其时间复杂度为■

用FE算法在图1中可选得一条符合条件的最优路，即欧拉回路：■。但符合条件的欧拉回路并不唯一，■也是满足条件的一条欧拉回路。

2.快递员负责的投递区域对应的街道图是非欧拉图

因为所对应的街道图是非欧拉图，而快递员要从快递公司出发，他必须经过由他负责投递的每条街道至少一次，并回到快递公司，因此有些街道要走不止一次。重复走某条街道相当于在街道图中为该街道添加一条重边。问题转化为在图中添加一些重边，构造成一个欧拉图并且要求添加的重边的权数之和最小。

把一个非欧拉图通过添加重边变成欧拉图，也就是通过添加重边把图中每个顶点的度数均变为偶数。因此，在添加重边时，很明显应该选择某个奇度顶点为端点添加重边，如果重边的另一端点也是奇度顶点，那么这条重边将这两个奇度顶点均变为偶度顶点；如果重边的另一端点是偶度顶点，则添加重边后，还必须从偶度顶点出发再添加一条重边与其他一个奇度顶点相连，因为原来的偶度顶点又变成了奇度顶点。

添加重边时还要注意两个原则：（1）不能重复添加重边，重复的重边应成对去掉，这样并不改变每一个顶点的奇偶性；（2）每一个圈上添加的重边的总长不能超过圈长的一半，否则应将此圈上添加的重边去掉，改在此圈上原来没有添加重边的路线上添加重边，这样也不改变每一个顶点的奇偶性。

以上两个原则既保证了添加重边后每个顶点都是偶度顶点，又保证了添加重边的总长最短。因此，添加重边后的街道图必存在欧拉回路。根据FE算法，即可找到满足条件的最优线路。下面看一具体的例子。

假设某快递公司的某快递员负责的投递范围为郑州市二七区的中原路以南、陇海路以北、大学路以西、嵩山路以东的范围. 以街道的交叉口为顶点，街道为边，街道的长度（单位：百米）为权数建立一个加权图，如图2所示。

在这个图中，街道的交叉点共有16个，但三次点有12个，因此要想构造出欧拉图，需要添加的重边至少有6条。根据添加重边的原则，每一个圈上添加的重边的总长不能超过圈长的一半，根据街道图的特点，图中包含的圈比较多，但很明显，大圈之中包含着小圈，故只要每个小圈中添加的重边的权数不超过圈长的一半，那么在大圈中必然也满足添加重边的权数不超过圈长的一半。因此，我们容易得到图3、图4两种添加重边的方案，

图3的方案是从N 点出发增加3条重边，最终将街道图的每个顶点均为偶度顶点，图4的方案是添加重边IJ ，把顶点J 变成了奇度顶点，再添加重边JK 将J，K 均变为偶度顶点。根据各边的权数大小，可知这两种方案添加的重边的权数之和是相等的，也是最小的。 假设快递公司在N 点，从图3、图4中，可分别找到一条欧拉回路：

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

快递员沿着这两条路线派送快件，即是最优路线。 由于FE算法中，欧拉回路不唯一，所以快递员派送快件的最优路线也不唯一。

参考文献：

[1]王树禾.图论[M].北京：科学出版社，2009.

[2]王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京：北京大学出版社，2011.

[3]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2010.endprint

摘 要：随着网络的普及，“网购”的流行，导致快递员派送快件的工作量增大。本文根据快递员投递快件的实际问题建立图论模型，利用图论中求欧拉回路的算法，为快递员设计最优投递路线，从而节约快递员的工作时间，减少其劳动强度，提高劳动效率。

关键词：欧拉图；欧拉回路；权数

图论是以图为研究对象的数学分支，近年来发展迅速，应用非常广泛. 它已经广泛地应用在物理学、化学、控制论、信息科学、科学管理、电子计算机等各个领域. 在实际生活、生产和科学研究中，有很多问题都可以用图论的理论和方法来解决。

随着网络的普及，“网上购物”成为时下比较流行的一种购物方式，它有着价格比实体店优惠、购物不受时间限制、方便、快捷的优点，还可以送过货上门，足不出户就能买到所需要的物品. 网上购物的流行，促使了快递行业的快速发展，“快递”成了妇孺皆知的词语了，但这也无疑加大了快递员的工作量. 本文根据实际问题建立图论模型，利用图论的理论和方法设计合理的投递路线，以减少快递员的工作时间和劳动强度，提高其劳动效率。

一、图论概念介绍

定义1. 1称数学结构■为一有向图，其中V（G）是非空集合，■是从集合E（G）到V（G）×V（G）的一个映射。称V（G）和E（G）分别为图G的顶点集合和边集合，■为G的关联函数. 若■，则简写成e=uv，称u是有向边e的尾，v为有向边e的头。 若图G为无向图，e=uv时，称顶点u与v是边e的端点。 若■，称e1与e2是重边。

定义1. 2在顶边交错链■中，■■■且■，则称W是图G的一条道路，其中允许vi=vj或ei=ej，i≠j，称Vo是W的起点，Vk是W的终点，K为路长，■称为W的内点。 各边相异的道路称为行迹，各顶相异的道路称为轨道，记成P（Vo，Vk），起点与终点重合的道路称为回路，起点与终点重合的轨道叫圈，长K的圈称为K阶圈；u，v两顶的距离是指u与v为起止点的最短轨道的长度，记成d（u，v），若存在道路以u，v为起止顶，则称u与v在图G中连通，G中任二顶皆连通时，称G为连通图。

定义1. 3 设G是连通的无向图，在图G中包含一切边的行迹叫做欧拉行迹，包含一切边的闭行迹叫做欧拉回路。若G中存在欧拉回路，则称G为欧拉图。

定理1. 1连通图G是欧拉图的充分必要条件是对任意的V∈V（G），d（v）是偶数，其中d（v）表示v的次数，即与v相关联的边数。

定义1. 4图G中的桥是指G中的一边e∈E（G），使得G-e的连通分支数增加。

二、模型的建立

这个问题的实际模型为：快递员从快递公司选好快件去投递，然后返回快递公司，他必须经过由他负责投递的每条街道至少一次，为这位快递员设计一条投递线路，使其行走的路程最短，耗时最少。

该问题的图论模型为：把快递员所负责的投递区域看成一个加权的连通图G，其顶点为街道的交叉口，边为每条街道，权为每条街道的长度（正数）。快递员的最优投递路线即为求G的一个包含一切边（至少一次）的回路W，使这条回路W的总权数最小. 若对G中对每条边e∈E（G），用一非负实数w（e）表示其权，求G的包含一切边的回路W，使得W的总权数■。

三、问题的解决

1.快递员负责的投递区域对应的街道图是欧拉图若快递员负责的投递区域对应的街道图G是欧拉图，根据定义1. 3，G中必含有欧拉回路，即包含G的一切边的闭行迹. 那么所求的最优投递路线就是G的一条欧拉回路。

根据定理1. 1，如果某快递员所负责的投递区域的街道图中没有奇顶点（顶点的次数是奇数），那么他就可以从快递公司出发，经过每个街道一次，且仅一次，最后回到快递公司。

尽管由定理1. 1可以很轻松地判定给定的街道图是否为欧拉图，但如果沿着一条随意的路线走，也是无法找到欧拉回路的. 假如街道图如图1，如果按照图中箭头所示的方向从顶点V6出发走了3步以后，就无法再进行下去了。其失败的原因是用了V6V5边之后，在未用过的边的导出子图中V5V7是桥，提前过桥的后果是断了去左侧的5-圈的后路。

因此，非必要时，不要通过未用过的边的导出子图的桥，根据这一思路，1921年，Fleury设计了一个求欧拉回路的有效算法，简记为FE算法：

（1）任取■，令Wo=Vo，

（2）设路■已选定，则从E（G）-E（W）中选一条边ei+1，使得ei+1与vi相关联，且非必要时，ei+1不要选G-E（W）的桥。

（3）反复执行（2），直至每边皆入选为止。

FE算法是有效算法，其时间复杂度为■

用FE算法在图1中可选得一条符合条件的最优路，即欧拉回路：■。但符合条件的欧拉回路并不唯一，■也是满足条件的一条欧拉回路。

2.快递员负责的投递区域对应的街道图是非欧拉图

因为所对应的街道图是非欧拉图，而快递员要从快递公司出发，他必须经过由他负责投递的每条街道至少一次，并回到快递公司，因此有些街道要走不止一次。重复走某条街道相当于在街道图中为该街道添加一条重边。问题转化为在图中添加一些重边，构造成一个欧拉图并且要求添加的重边的权数之和最小。

把一个非欧拉图通过添加重边变成欧拉图，也就是通过添加重边把图中每个顶点的度数均变为偶数。因此，在添加重边时，很明显应该选择某个奇度顶点为端点添加重边，如果重边的另一端点也是奇度顶点，那么这条重边将这两个奇度顶点均变为偶度顶点；如果重边的另一端点是偶度顶点，则添加重边后，还必须从偶度顶点出发再添加一条重边与其他一个奇度顶点相连，因为原来的偶度顶点又变成了奇度顶点。

添加重边时还要注意两个原则：（1）不能重复添加重边，重复的重边应成对去掉，这样并不改变每一个顶点的奇偶性；（2）每一个圈上添加的重边的总长不能超过圈长的一半，否则应将此圈上添加的重边去掉，改在此圈上原来没有添加重边的路线上添加重边，这样也不改变每一个顶点的奇偶性。

以上两个原则既保证了添加重边后每个顶点都是偶度顶点，又保证了添加重边的总长最短。因此，添加重边后的街道图必存在欧拉回路。根据FE算法，即可找到满足条件的最优线路。下面看一具体的例子。

假设某快递公司的某快递员负责的投递范围为郑州市二七区的中原路以南、陇海路以北、大学路以西、嵩山路以东的范围. 以街道的交叉口为顶点，街道为边，街道的长度（单位：百米）为权数建立一个加权图，如图2所示。

在这个图中，街道的交叉点共有16个，但三次点有12个，因此要想构造出欧拉图，需要添加的重边至少有6条。根据添加重边的原则，每一个圈上添加的重边的总长不能超过圈长的一半，根据街道图的特点，图中包含的圈比较多，但很明显，大圈之中包含着小圈，故只要每个小圈中添加的重边的权数不超过圈长的一半，那么在大圈中必然也满足添加重边的权数不超过圈长的一半。因此，我们容易得到图3、图4两种添加重边的方案，

图3的方案是从N 点出发增加3条重边，最终将街道图的每个顶点均为偶度顶点，图4的方案是添加重边IJ ，把顶点J 变成了奇度顶点，再添加重边JK 将J，K 均变为偶度顶点。根据各边的权数大小，可知这两种方案添加的重边的权数之和是相等的，也是最小的。 假设快递公司在N 点，从图3、图4中，可分别找到一条欧拉回路：

（1）NQFEDPBCDEONMLKABPONMHILKJIHON

（2）NOPBCDEFQHIJKABPDEONMLIJKLMHQN

快递员沿着这两条路线派送快件，即是最优路线。 由于FE算法中，欧拉回路不唯一，所以快递员派送快件的最优路线也不唯一。

参考文献：

[1]王树禾.图论[M].北京：科学出版社，2009.

[2]王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京：北京大学出版社，2011.

[3]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2010.endprint