道路改造项目中的碎石运输的设计

一 摘要

本文讨论了道路改造项目中的碎石运输的设计。

首先,我们对于铺路的模式、碎石临时堆放点的数量、Ｓ１和Ｓ２采石点的供应区域进行了定量的讨论。这样之后,我们对整个运输方案已经有了一个整体的把握。在此基础上,我们提出泛函规划模型和非线性规划模型。

泛函规划模型将变分法和规划方法相结合,可以求得最优解。得出的结果为：需要修建7个码头。总费用为15.41亿。从S1采石厂取碎石101.72万立方米。从S2采石厂取碎石48.28万立方米。从S1采石厂有5条线路从水路进行运输,其中有一条需逆流运输；从S2采石厂铺设3条临时道路进行矿石运输。 在对S1、S2碎石供应方式的进一步讨论的基础上,建立了非线性规划模型。利用罚函数法进行搜索得到的结果为：需要修建7个码头。总费用为：15.82亿元。从S1采石厂取碎石99.75万立方米。从S2采石厂取碎石50.25万立方米。仍然有一条水运道路逆流而上。为了说明我们结果的最优性,我们对于总费用的区间进行了定量的估计。我们发现：当临时堆放点的数目在10个以,无论如何修建临时道路和临时码头,,总费用必然会超过13.82亿。如果临时堆放点的数目在5个以,必然会超过15.32亿。可见我们的结果是很接近最优解的。 我们对各种临界状态进行了讨论。我们发现：对于AB道路上的任一点,当其在点P〔133,100〕之右时,就该由S2采石点供应碎石。P点以左的区域应该有由S1厂进行供应。就AP段而言,存在一临界点Q〔83,100〕,当某点在Q左时,应该由S1出发,沿河流上游运送碎石到m4点,再从m4出发,沿AB运至该点,当某点在Q右时,应该由S1出发,先沿河流上游运送碎石到m4,接着河流下游顺流而下,最后沿一条垂直于河流的临时道路运至该点。

1 / 19

文中所建立的两个模型,论证充分、严密,尤其是泛函规划模型可以得到理论上的最优解,得到的结果好。临界状态的确定,对于运输方案设计,很有参考价值。对于总费用下界的定量讨论,对于模型和算法的评价,很有借鉴意义。 二 问题重述

在一平原地区要进行一项道路改造项目,在A , B 之间建一条长200km ,宽15m ,平均铺设厚度为0 . 5m 的直线形公路。为了铺设这条道路,需要从51 , S2 两个采石点运碎石。1 立方米碎石的成本都为60 元。〔S1 , S2 运出的碎石已满足工程需要,不必再进一步进行粉碎。〕51 , 52 与公路之间原来没有道路可以利用,需铺设临时道路。临时道路宽为4m ,平均铺设厚度为0 . lm 。而在A , B 之间有原来的道路可以利用。假设运输1 立方米碎石Ikm 运费为20 元。此地区有一条河,故也可以利用水路运输：顺流时,平均运输1 立方米碎石Ikm 运费为6 元；逆流时,平均运输1 立方米碎石Ikm 运费为10 元。如果要利用水路,还需要在装卸处建临时码头。建一个临时码头需要用10 万元。

建立一直角坐标系,以确定各地点之间的相对位置：

A < O , 100 > , B < 200 , 100 > , 51 < 20 , 120 > , 52 < 180 , 157 〕。 河与AB 的交点为m4 < 50 , 100 > < m4 处原来有桥可以利用〕。河流的流向为m1 一m7 , m4 的上游近似为一抛物线,其上另外几点为ml < 0 , 120 > , m2 < 18 , 116 > , m3 < 42 , 108 > ; m4 的下游也近似为一抛物线,其上另外几点为m5< 74 , 80 > , m6 < 104 , 70 > , m7 < 200 , 50 〕。 桥的造价很高,故不宜为运输石料而造临时桥。 此地区没有其它可以借用的道路。

为了使总费用最少,如何铺设临时道路〔要具体路线图〕；是否需要建临时码头,

2 / 19

都在何处建；从51 , 52 所取的碎石量各是多少；指出你的方案的总费用。 三 问题分析

题中已给出两个采石点,需要我们来设计从两个采矿点s1,s2运送碎石到AB路上并对其进行改造的线路。

工程的总费用由以下几个部分构成：改造AB所需的碎石的成本、将这些碎石从采石点运到AB的费用、将已经运到AB上的碎石在AB上铺开所需的费用、修建临时道路的费用、修建码头的费用。这五部分中,将这些碎石从采石点运到AB的费用、将已经运到AB上的碎石在AB上铺开所需的费用、修建临时道路的费用、修建码头的费用。这五部分中,将这些碎石从采石点运到AB的费用、将已经运到AB上的碎石在AB上铺开所需的费用和修建临时道路的费用将占主要部分。

显然,如果沿着一条单一的线路进行运输,由于AB公路空间跨度太长,此方案并非最优,因而不论是从s1和还是s2出发的线路都应该是一个稍微复杂一些的网状结构。与陆地运输相比较,水路运输一方面不需要铺设临时道路〔简单的计算可以知道,这部分的费用通常是千万元级的〕,另一方面,运送同样数量的碎石在相等的距离围,水路运输的费用仅仅为陆路运输的3/10,而水路运输修建的临时码头所需的10万元,与庞大的运费相比,则显得微不足道。因而,合理而充分的发挥水路运输的优势,将会使总费用大大减少。修桥的费用很到高,因而我们不考虑建桥。

事实上,我们就是要在所有可能的轨线 中找出满足各种空间约束及资源约束并使沿着这些轨线运输石料铺路的费用最小的一些轨线。在这方面,泛函分析有无可比拟的优势,我们可以将泛函分析与规划相结合来找到最优解。另一方面,在对运输线路最优解的特性有了一些认识之后,我们可以从总体

3 / 19

上设计出运输线路的模式,在此基础上,我们也可使用规划来解决这个问题。对于最优解特性的充分认识,将可以保证我们获得非常接近最优解的结果。 四 基本假设

1.车辆空载回来的费用认为已经包含在石料的运费中,因而可以不予考虑,其实实际情况也往往是这样。

2.桥的造价很高,与其他费用相比,可以看作无穷大。 3.河流的宽度足够用于在河的两岸同时建两个码头。 4.渡河的费用可以忽略不计。 5．此地区没有其它可以借用的道路。

6.因为河流的上下游都近似为抛物线,因而在我们的后续处理中,可以将其按照抛物线对待。

7．实际修建的道路可以完全按照我们设计的道路修建,不需要因为某处有村庄、湖泊、建筑物等而绕道。 五 符号说明

：第i段道路的长度。 ：第i条道路的运量。

：改造AB所需的碎石的成本。4：将改造AB所需的碎石从采石点运到AB的费用。

：将已经运到AB上的碎石在AB上铺开所需的费用。 ：修建临时道路的费用。 ：修建码头的费用。

R：从S1向河流的上游所做垂线与河流的交点。

P：AB道路上 s1采石点供应区域与s2采石点供应区域之间的分界点。

4 / 19

n：碎石临时堆放点的数目。 六 模型的建立与求解

6.1初步分析 6.1.1河流轨迹的辨识

河流的上下游的轨迹近似为抛物线,可使用已知的几个点ml < 0 , 120 > , m2 < 18 , 116 > , m3 < 42 , 108 >,m4 < 50 , 100 >,m5< 74 , 80 > , m6 < 104 , 70 > , m7 < 200 , 50 〕进行曲线拟合,拟合的结果为〔以横轴为x轴,纵轴为y轴〕： 河流上游： 河流下游：

6.1.2合理的铺路模式 Fig 1

如图所示,假设一堆碎石已被运送到AB上的某处M,将这堆碎石在道路AB上铺开,从M处铺至N处,所花的费用为：

可见,铺路的费用随着路长是以平方级增长的。对于上面的模式,我们考虑,如果不是从M开始,只向一边铺路,而是向左向右都展开的模式,如图2示： M N O Fig 2

在道路总长度仍为l的情况下,此时的费用为：

可以比原来的节约费用：

5 / 19

显然,在 一定的条件下,当a、 b相等时,上述差值最大,铺路时尽量从中心向两边对称展开可以在很大程度上节省费 6.1.3碎石的临时堆放点的数目估计

如上文所述的点M,是某条道路与AB的交点,碎石可先从采石点运至该处,再从M点开始向两边铺开,我们称这种点为碎石的临时堆放点。 显然,如果只有极少数目的碎石临时堆放点,将会使改造AB的费用大大增加〔因为费用是按平方级增长的〕。合理的增加碎石临时堆放点的数目将会使从每个堆放点铺开的费用大大减小。在道路改造长度不变的情况下,将会使改造AB的总费用大大降低。 下面,我们给出一组数据,来定量说明： 表1

碎石临时堆放点的数目〔n〕 将已经运到AB上的碎石在AB上铺开所需的费用 〔元〕 1 1.5e9 2 7.5e8 3 5e8 4 3.75e8 5 3e8 6 2.5e8 7 2.1429e8 8 1.875e8

6 / 19

9 1.6667e8 10 1.5e8 11 1.3636e8 12 1.25e8 13 1.1538e8 14 1.0714e8 15 1e8

从上述结果发现：

1．随着临时堆放点数目的增加,铺设AB道路的费用迅速下降。√ 2．当临时堆放点数目增加到8个左右时,铺设AB道路的费用下降已较缓慢。这时,如果再增加临时堆放点, 不再有明显的下降,同时,增加一个临时堆放点,就要多修一部分的临时道路,从而导致总费用的增加。此时,就不宜再增加临时堆放点了,因而,合理的临时堆放点数目可以取8个。 6.1初步分析 6.1.1河流轨迹的辨识

河流的上下游的轨迹近似为抛物线,可使用已知的几个点ml < 0 , 120 > , m2 < 18 , 116 > , m3 < 42 , 108 >,m4 < 50 , 100 >,m5< 74 , 80 > , m6 < 104 , 70 > , m7 < 200 , 50 〕进行曲线拟合,拟合的结果为〔以横轴为x轴,纵轴为y轴〕： 河流上游：

7 / 19

河流下游：

6.1.2合理的铺路模式 Fig 1

如图所示,假设一堆碎石已被运送到AB上的某处M,将这堆碎石在道路AB上铺开,从M处铺至N处,所花的费用为：

可见,铺路的费用随着路长是以平方级增长的。对于上面的模式,我们考虑,如果不是从M开始,只向一边铺路,而是向左向右都展开的模式,如图2示： M N O Fig 2

在道路总长度仍为l的情况下,此时的费用为： 可以比原来的节约费用：

显然,在 一定的条件下,当a、 b相等时,上述差值最大,铺路时尽量从中心向两边对称展开可以在很大程度上节省费用。 6.1.3碎石的临时堆放点的数目估计

如上文所述的点M,是某条道路与AB的交点,碎石可先从采石点运至该处,再从M点开始向两边铺开,我们称这种点为碎石的临时堆放点。 显然,如果只有极少数目的碎石临时堆放点,将会使改造AB的费用大大增加〔因为费用是按平方级增长的〕。合理的增加碎石临时堆放点的数目将会使从每个堆放点铺开的费用大大减小。在道路改造长度不变的情况下,将会使改造AB的总费用大大降低。 下面,我们给出一组数据,来定量说明：

8 / 19

表1

碎石临时堆放点的数目〔n〕 将已经运到AB上的碎石在AB上铺开所需的费用 〔元〕 1 1.5e9 2 7.5e8 3 5e8 4 3.75e8 5 3e8 6 2.5e8 7 2.1429e8 8 1.875e8 9 1.6667e8 10 1.5e8 11 1.3636e8 12 1.25e8 13 1.1538e8 14 1.0714e8 15 1e8

从上述结果发现：

1．随着临时堆放点数目的增加,铺设AB道路的费用迅速下降。√

9 / 19

2．当临时堆放点数目增加到8个左右时,铺设AB道路的费用下降已较缓慢。这时,如果再增加临时堆放点, 不再有明显的下降,同时,增加一个临时堆放点,就要多修一部分的临时道路,从而导致总费用的增加。此时,就不宜再增加临时堆放点了,因而,合理的临时堆放点数目可以取8个。 6.2.2泛函规划模型

受上述6.2.1模型的启发,对于本文题中设计的复杂线路图,我们这样考虑：先寻找一条从S1〔或S2〕运送 的碎石到AB上某点的最优路线,将这些碎石在AB上铺开。然后将AB上已铺区域从曲线的终点集〔即道路AB〕中除去。再依次寻找从从S1〔或S2〕运送 〔i=1,2．．．８〕的碎石到AB上某点的最优路线,并将这些碎石在AB上铺开。运用泛函分析的方法,可以保证每一条路线都是最优的。即每步都是局部最优。但这并不能保证全局最优。主要是由于各条路运量的分配并不一定合理从而导致冲突,此时,我们将规划化和泛函分析相结合,将各条线路上的运量合理分配即可求得全局最优解。

设从采石点S1出发有m条路到AB上,从采石点S2出发有n条道路到AB上。各条线路的运量分别为 从s1出发的5条道路与AB的交点为〔x1,100〕,〔x2,100〕,〔x3,100〕,〔x4,100〕,〔x5,100〕,从s2出发的3条道路与AB的交点为〔x6,100〕,〔x7,100〕,〔x8,100〕。 建立以下泛函规划模型： 其中,

S.t 碎石总量约束： 铺完约束：

10 / 19

〔i,j=1,…,8〕 位置约束： 〔i=1,…,8〕 6.3 泛函规划模型结果

求解上述泛函规划模型,得到结果如下： 1. 修路总费用：15.41亿元；

2. 从S1采石厂取碎石101.72万立方米。从S2采石厂取碎石48.28万立方米。

3. 需要修建码头数：7个 坐标分别为： 表2

码头 1 2 3 4 5 6 7

横坐标 18.72 9.92 22.96 34.22 86.08 50 106.12 纵坐标 115.72 118.23 114.23 108.11 76.57 100 68.55 4．码头分布及临时道路的具体线路图如下： Fig4〔疑问：为何不运到中点再铺开？〕 6.4非线性规划模型

6.4.1 s1与s2碎石供应区域分界点的确定

要向AB上任意一点运送碎石,可以选择从s1经陆路运送,从s1经水路运送,从s2经陆路运至,从s2经水路运至〔显然,在题目中所给特定条件下,为了保证总费用最低,这种方式几乎不被利用到〕。

11 / 19

在空间位置上,公路AB上碎石来自采石点s1和s2的区域存在一个分界点。显然某点越靠向B端,就越适合于从s2运碎石到该点,当从s1运送碎石到某点的费用与从s2运送碎石到该点的费用相当的时候,该点就可以作为s1供应区域与s2供应区的分界点。

经过计算点P〔133,100〕应为s1与s2供应区的分界点,P点以右的区域〔133,100〕--〔200,100〕适合于由s2采石点供应碎石。P点以左〔0,100〕--〔133,100〕的区域适合与有采石点s1供应碎石。

这样,从s2出发的应该大致有三条运输线路,从s1出发的大致应该有5条运输线路。

6.4.２ s1采石点供应方式的确定

显然从点A到点m4的区域应该由s1经过水路来运输碎石,因为建桥的费用认为是无穷大,在从m4到点P的路段该由什么方式来运输碎石呢？ 先来看看以下数据： 表3

公里数〔n〕 20万立方米碎石n公里运输费 新修n公里临时公路费用 10 4e6 4e5 15 4e7 9e5 20 8e7 16e5 25 1e8 25e5 30 1.2e8 36e5 35 1.4e8 49e5

12 / 19

40 1.6e8 e5 45 1.8e8 81e5 50 2e8 1e7

由上表可以看到,在我们将会使用到的围,运送碎石的运费远远大于为运送碎石所需修建的临时公路的费用,因而在比较运输方案的优劣时,在极大程度上取决于运送石料的运费,故我们可以只考虑运费。

下面,我们将会证明,AB上m4到P段的碎石也需要从s1经过水路运到。也就是说,不需要从s1运出的直接修建临时道路到AB上,这就意味着从s1运出的碎石都应该要经过水路。 证明：

显然,在不修建桥的情况下,从s1适合A m4段的碎石都应该经过水路。 对于m4 P段上的任意一点Q〔x,100〕沿着陆路运输m立方米的碎石到该处所需最小运费c为：

而设水路运输n立方米的碎石到该处所需的 为： 取R为切点, 当 ：

因此,从s1运出的碎石都要经过水路运输。 6.4.3 模型建立 设从

s1

出发的

5

条道路进入水路的点分别为

〔x1,y1〕,,,,。

从s1出发的5条道路由水运转陆运得码头的修建点分别为〔x6,y6〕,

13 / 19

〔x7,y7〕,〔x8,y8〕,〔x9,y9〕,〔x10,y10〕。

从s1出发的5条道路与AB的交点为〔x11,100〕,〔x12,100〕,〔x13,100〕,〔x14,100〕,〔x15,100〕。

从s2出发的3条道路与AB的交点为〔x16,100〕,〔x17,100〕,〔x18,100〕。 从s1出发的5条道路的运量分别为n1,n2,n3,n4,n5。 从s2出发的3条道路的运量分别为n6,n7,n8。 则原问题转化为如下的非线性规划模型：

其中,改造AB路所需石料的成本：改造AB路所需石料的运费：修建临时道路的费用： 修建码头的费用： S．t． 轨迹约束： 〔i=1,…,10〕 碎石总量约束： 铺完约束：

〔i=1,…,7；j=i+10〕 位置约束： 〔i=1,…,7〕 〔i=1,…,7〕

〔i=8,9,10,13,14,15〕

14 / 19

〔i=8,9,10〕 〔i=16,17,18〕 6.5模型求解

该问题是典型的有约束非线性规划问题。采用罚函数法搜索的得到的结果。

1．总费用：15.82亿元； ２．需要修建码头数：7个 码头位置 表4

码头 1 2 3 4 5 6 7

横坐标 18.72 10.12 23.26 37.22 85.8 50 106 纵坐标 116 117.83 114.63 110.11 75.57 100 69.45 3．码头分布及临时道路的具体线路图如下： Fig5

４．临时堆放点 表6

临时堆放点 1 2 3 4 5 6 7 8

X坐标 6.12 19.26 34.22 94.13 114.33 141.5 162.51 187.45 ５．运量分配： 表7

15 / 19

运输

线路 1 2 3 4 5 6 7 8

运量〔百万立方米〕 0.09 0.105 0.18 0.4125 0.21 0.1275 0.1875 0.1875 七 结果分析 7.1逆流运输

观察上述结果,我们可以发现,存在一条逆流而上的道路,即我们在Fig4中用红色表示出来的部分,此道路用于从s1运输碎石到靠近A处进行道路改造。

此道路的存在,显然是必要的。要改造A点附近的道路,应该由s1经水路运送碎石到该段。经济起见,碎石应该被运至离A处较近的一点。这样一方面碎石的运费比较低,另一方面,改造这段路所需费用也会比较低。也就是说,碎石应该朝向A点运输,逆流而上,而非顺流而下。 7.2最小费用估计

为了对我们的结果进行一个定量的检验,下面我们来对总费用的区间作一个估计。我们希望找出总费用的一个下界。

前面,我们已经提到s1与s2供应分界点大致应该为P〔133,100〕,P点右边的区域应该都由s2供应,显然这部分碎石被运至AB上,所需修建的临时道路的长度至少应该为57km,即使我们认为所有的碎石都沿此最短的临时道路运输,那么这部分碎石在临时道路上的运费也会达到5.73亿。 后面,我们将会说明,在AB路上存在一点Q,在m4Q之间的任意一点,碎石从s1经河流上游到m4再沿AB到达该处比较合算,在PQ之间的任意一点,碎

16 / 19

石从s1经河流上游到m4,再沿河流上游顺流而下最后经陆路〔临时公路〕到达AB上比较合算。

此时,碎石被运至QP段的任何一点,其运费都会超过碎石从s1经河流上游到达m4再沿AB到达Q处的运费,即使按照将碎石运至Q点处的运费计算。这段的运费也至少可以应该为3.63亿。

对于Am4区域上的一点。从s1到该点的运费都会超过碎石从s1经河流上游到大m4的运费。即使按照只运到m4计算运费,该段的运费至少也应该为1.9亿。

铺设AB所需碎石的成本费为0.9亿。

即使我们只修建一条s2垂直于AB的临时道路。这段路的修建费用也应该为；因而,不考虑将碎石在AB上铺开的费用时,总费用也至少为：此时,我们给出一组临时堆放点数目与总费用下界的对应关系。 表8

碎石临时堆放点的数目〔n〕 铺设AB道路最小费用<元> 总费用的下界估计〔元〕 1 1.5e9 27.32e8 2 7.5e8 19.82e8 3 5e8 17.32e8 4 3.75e8 16.07e8 5 3e8 15.32e8 6 2.5e8 14.82e8

17 / 19

7 2.1429e8 14.4629e8 8 1.875e8 14.195e8 9 1.6667e8 13.9867e8 10 1.5e8 13.32e8 从上表可以看出：

1.不管如何铺设道路,如何修建码头,总费用也会超过12.32亿 2．当临时堆放点的数目在10个以,无论如何修建临时道路和临时码头,,总费用必然会超过13.82亿。如果临时堆放点的数目在5个以,必然会超过15.32亿。

3.上述的下界是在我们作了大量缩放的基础上并且忽略了码头,修建多条临时道路时的费用。在精确计算的基础上我们得出15.7亿的结果,这样的结果是非常靠近14亿,其最优性是显而易见的。 八 临界状态

下面我们来讨论几个比较有意义的临界状态。

1.如前所述,AB上的P点,坐标为〔133,100〕是s1采石点供应区域与s2采石点供应区域之间的分界点。AP段的碎石由s1供应比较合算。而PB段的碎石由s2供应比较合算。

2.前面我们已经证明过,从s1厂运出的碎石应该经过水路运输到AP段。对于m4P上的一点可以由两种方式运碎石到该段上：第一种方式,可以由s1出发经过河流上游到达m4处,在顺流而下从河流下游某处眼临时道路

18 / 19

运至AB上；第二种方式,由s1出发经过河流上游到达m4处,再沿AB道路运送。

假设m4P上某点坐标为〔x,100〕。则沿第一种方式运输时的单位运量运费为：

第二种方式下,假设从水路转入陆路的点为〔x1,y1〕,则这种方式下的单位运量的运费为：

将 对 求取最小值,可得〔ｘ１,ｙ１〕为从〔ｘ１,１００〕向河流下游所做垂线的垂足。

这就是说ＡＢ上Ｑ点〔１３３,１００〕可以作为方式一和方式二的分界点。

临界点的图如下 Fig6

九 模型的评价 优点：

〔1〕 本文将泛函分析与规划相结合,理论上可以求出最优解。 〔2〕 本文对临界状态进行了定量的讨论。论证严密

19 / 19