该问题仍需要建立规划模型来求解。在整个邮路网络中，各支局、县局和市局是网络的节点，现在需要从县局出发，在一定的条件下对各支局进行遍历，为了便于描述，令{}79,,2,1L =Zone 为节点集合，当{}73,,2,1L ∈i 时，i Z 表示各支局，编号同题目中一致；当{}78,77,76,75,74∈i 时，i Z 表示各县局，与县局j X (j=1,2,3,4,5)一致；当79=i 时，i Z 表示各市局。
在该问题中，我们的最终目标应该是运输成本最低，为了便于问题描述，引入变量：
⎩⎨
⎧≠=其他情况
，且到局回路是从,0j i j i X ,1k kij
x
这里，{}61,2,3,4,5,k ∈，其中6X 表示市局，其他情况表示县局，与问题中的编号一致；k X 局回路的意思是由k X 局邮车所负责的回路。
这样总运费最少就可以描述为：
Min ∑
∑∑==∈≠∈⋅⋅6
1,k k Zone i j
i Zone j kij ij
p x Dist
其中，p 表示邮路的运行成本，由题可知3=p (元/公里)。
在以上目标条件下，该邮路规划模型需要包含以下这些约束条件：
(1) 市局邮车必须到其所负责的邮局1次，包括县局及市局附近的支局，用数学表达式描述为：
∑≠∈=j
i Zone i ij x
,1
,6 6U j ∈∀
这里，6U 表示市局必须负责的邮局，6U ={}78,,59,58,L =i Z i (2) 市局邮车必须从其所负责的邮局出发1次，用数学表达式描述为：
∑≠∈=i
j Zone j ij x
,1
,6 6U i ∈∀
(3) 县局邮车或市局邮车必然到该县局所辖各支局一次，用数学表达式描述为：
1,,,,6=+
∑∑≠∈≠∈j
i Zone i ij
k j
i Zone i ij x
x
5,4,3,2,1,
=∈∀k U j k
这里，k U 表示k X 局必须负责的邮局。
(4) 县局邮车或市局邮车必然从该县局所辖各支局出发一次，用数学表达式描述为：
1,,,,6=+
∑∑≠∈≠∈i
j Zone j ij
k i
j Zone j ij
x
x
5,4,3,2,1,
=∈∀k U i k
(5) 邮车只在一个完成的回路上运行，可以用以下的数学表达式来加以约束：
k k k k kij k j i n DL j DL i n x n u u ≤+−≠+−≤−≤+−112,1
这里i u (n i ,,2,1L =)为额外附加变量，k n 为k X 局必须负责的邮局数，k DL 为k
X 所负责邮局编号的下限。
(6) 从k X 局出发的邮车应该等于该局拥有的邮车总数k MCN ：
{}k 73j ,6,5,4,3,2,1,,73,+≠∈∀=∑∈+且k MCN x
Zone
j k j
k k
(7) 回到k X 局的邮车应该等于该局拥有的邮车总数k MCN ：
{}k 73i ,6,5,4,3,2,1,73,,+≠∈∀=∑∈+且k MCN x
Zone
i k k
i k
(8) 邮车必须在一定的工作时间内运送邮件，市局邮车是从6：00到11：00这
段时间内运送邮件，所以市局每辆邮车跑完每个回路的时间不能超过5小时，即：
6
678
74
6731656010605MCN v Dist x x x ij ij Zone i j j ij Zone i j j ij ≤⋅++∑∑∑∑∑∑∈==∈==
(9) 县局的邮车也必须在一定的时间内运送邮件。设从市局到县局k X 的邮车从市局出发后到该县局所需的时间为k Time ，而该趟邮车走完该回路所需的总时间(total time)为k TT 。由于市局第一班次邮车是从6：00出发，而市局第二班次邮车在18：00到达市局，根据要求，该县局的邮车的运行时间为：
()[]()k k k k TT Time Time TT −=++−−−−1016118
所以对该县局邮车来说，其时间限制可以描述为：
()k
k ij kij kij MCN TT v Dist x x ⋅−≤⋅+∑∑∑∑10605 {}k 73j ,6,5,4,3,2,1+≠∈∀且k
(10) 变量有效性约束：
{}Z MCN x k kij ∈∈,1,0
至此，针对县局邮路的规划问题，可以建立如下的单目标规划模型： Goal : Min ∑
∑∑==∈≠∈⋅⋅6
1,k k Zone i j
i Zone j kij ij
p x Dist
Subject to :
∑≠∈=j
i Zone i ij x
,1
,6 6U j ∈∀ (1)
∑≠∈=i
j Zone j ij x
,1
,6 6U i ∈∀ (2)
1,,,,6=+∑∑≠∈≠∈j
i Zone i ij
k j
i Zone i ij
x
x
5,4,3,2,1,=∈∀k U j k (3)
1,,,,6=+
∑∑≠∈≠∈i
j Zone j ij
k i
j Zone j ij
x
x
5,4,3,2,1,
=∈∀k U i k (4)
k k k k kij k j i n DL j DL i n x n u u ≤+−≠+−≤−≤+−112,1 (5)
{}k 73j ,6,5,4,3,2,1,,73,+≠∈∀=∑∈+且k MCN x
Zone
j k j
k k (6) {}k 73i ,6,5,4,3,2,1,73,,+≠∈∀=∑∈+且k MCN x
Zone
i k k
i k (7)
6
678
74
6731656010605MCN v Dist x x x ij ij Zone i j j ij Zone i j j ij ≤⋅++∑∑∑∑∑∑∈==∈== (8)
(){}⎪⎩
⎪⎨⎧+≠∈∀⋅−≤⋅+∑∑∑∑k 73j ,6,5,4,3,2,110605且k MCN TT v
Dist x x k
k ij kij kij (9) {}Z MCN x k kij ∈∈,1,0 (10)
5.3 问题三的模型建立
问题3与问题2相比，仅县局所负责的支局可以自由选择，体现在模型中，就是模型的约束中变量的取值范围发生变化，所以该问题的数学模型为：
Goal : Min ∑∑∑==∈≠∈⋅⋅6
1,k k Zone i j
i Zone j kij ij
p x Dist
Subject to :
∑≠∈=j
i Zone i ij x
,1
,6 6U j ∈∀ (1)
≠∈i
j Zone j ,15
1,,,,6=+∑∑∑==≠∈≠∈k k j i Zone i ij k j
i Zone i ij x x ∑==∈∀51
k k k
U j (3)
15
1,,,,6=+∑
∑∑==≠∈≠∈k k i
j Zone j ij
k i
j Zone j ij
x
x
∑==∈∀5
1
k k k
U j (4)
k k k k kij k j i n DL j DL i n x n u u ≤+−≠+−≤−≤+−112,1 (5)
{}k 73j ,6,5,4,3,2,1,,73,+≠∈∀=∑∈+且k MCN x
Zone
j k j
k k (6) {}k 73i ,6,5,4,3,2,1,73,,+≠∈∀=∑∈+且k MCN x
Zone
i k k
i k (7)
667874
6731656010605MCN v Dist x x x ij ij Zone i j j ij Zone i j j ij ≤⋅++∑∑∑∑∑∑∈==∈== (8) (){}⎪⎩
⎪⎨⎧+≠∈∀⋅−≤⋅+∑∑∑∑k 73j ,6,5,4,3,2,110605且k MCN TT v
Dist x x k
k ij kij kij (9) {}Z MCN x k kij ∈∈,1,0 (10) 说明：该模型除了约束(3),(4)与问题2的数学模型不同外，其他约束均相同，变量的意义也一致。 5.4问题四的模型建立
该问题与问题2的不同在于县级邮局可以设在该县的任意邮局上，所以该问题的数学模型还可以借鉴问题2的模型，只是需要对县级由局所设的位置进行遍历。
设k U i ∈∀，{
}5,4,3,2,1∈k ，这里k U 仍表示k X 局所辖支局的编号，而该县局在所有节点中的编号为k +73，根据编程过程中的两变量换值的思想，县局的选址过程可
以描述为：
MP i i k k MP ==++=,73,73
其中MP 为中间变量(middle parameter)。
所以，针对该问题只需在问题2的模型中加上该项约束就可以，所以该问题的模型可以描述为：
Goal : Min ∑∑∑==∈≠∈⋅⋅6
1,k k Zone i j
i Zone j kij ij
p x Dist
Subject to :
≠∈j
i Zone i ,∑≠∈=i
j Zone j ij x
,1
,6 6U i ∈∀ (2)
1,,,,6=+∑∑≠∈≠∈j
i Zone i ij
k j
i Zone i ij
x
x
5,4,3,2,1,=∈∀k U j k (3)
1,,,,6=+
∑∑≠∈≠∈i
j Zone j ij
k i
j Zone j ij
x
x
5,4,3,2,1,
=∈∀k U i k (4)
k k k k kij k j i n DL j DL i n x n u u ≤+−≠+−≤−≤+−112,1 (5)
{}k 73j ,6,5,4,3,2,1,,73,+≠∈∀=∑∈+且k MCN x
Zone
j k j
k k (6) {}k 73i ,6,5,4,3,2,1,73,,+≠∈∀=∑∈+且k MCN x
Zone
i k k
i k (7)
667874
6731656010605MCN v Dist x x x ij ij Zone i j j ij Zone i j j ij ≤⋅++∑∑∑∑∑∑∈==∈== (8) (){}⎪⎩
⎪⎨⎧+≠∈∀⋅−≤⋅+∑∑∑∑k 73j ,6,5,4,3,2,110605且k MCN
TT v
Dist x x k
k ij kij kij (9) MP i i k k MP ==++=,73,73，k U i ∈∀，{}5,4,3,2,1∈k (10)
{}Z MCN x k kij ∈∈,1,0 (11) 说明：该模型除了约束(3),(4)与问题2的数学模型不同外，其他约束均相同，变量的意义也一致。
六、模型求解
6.1 问题一求解
问题一求解过程涉及的数据规模庞大，普通的优化软件难以求解。我们先给出一个较优解，然后再利用我们的算法求出最优解。 6.1.1基于最小生成树的试探解
Step1：先生成x1县区邮政网络的最小生成树（利用lingo），如图2所示。 Step2：由最小生成树的分支情形将邮政网络图分成三个子巡回，如图3所示。