数学建模旅游问题C2(5)

301015

IHGJK s D t LBA CE MF

N O P R

Q

这样时间为：51.45天。

下面进行局部调整：其中若羌（包括楼兰）、吐鲁番、乌鲁木齐（包括天山）和伊宁（包括伊犁）根据题目要求，是最好尽可能去旅游的点，不宜去掉。

以这样的原则，得到如下路线：(综合各方面因素，我们决定精确到小数点后一位)

a：乌鲁木齐→t→伊宁→t→库车→阿克苏→阿图什→喀什→和田→若羌→库尔勒→乌鲁木齐 用时：30.2天 10个城市

b：乌鲁木齐→t→伊宁→t→库车→和田→若羌→库尔勒→吐鲁番→乌鲁木齐 用时：27.8天 8个城市

c：乌鲁木齐→哈密→鄯善→吐鲁番→库尔勒→若羌→和田→t→乌鲁木齐用时：27.2 9个城市

d：乌鲁木齐→昌吉→石河子→s→克拉玛依→塔城→阿拉泰→哈密→鄯善→吐鲁番→库尔勒→乌鲁木齐 用时：30.6 10个城市

a路线虽然最多，但缺少吐鲁番；

b路线虽然不是很多，但是题目中向往的城市均有； c路线缺少伊宁；

d路线缺少伊宁和若羌，但却游玩了北部地区。 根据每个城市的消费：“城市分”和时间，算出总的花费：

a=8697+444＝9141 ￥ b=8097+463＝8560 ￥ c=6618+483＝7101 ￥ d=8569+459＝9028 ￥

5.2 60天分两次完成

因为题要求是在两年之内游完新疆，那么我们有理由相信，时间是充裕的，

最佳旅游线路的设计

20

301015

而实际要求成为消费最小。

不难知道，求出路上的时间最少，而且又是分两次走，这类似于多个推销员问题，而这类问题在目前也是不可解决的。我们知道，求最小路径和最小树是在一定程度上对这类问题近似。所以，我们围绕这两种“最优”路线做局部搜索，从而算出近似最优解。

首先，用Dijkstra算法与乌鲁木齐到各点的最小时间为： 昌吉：0.02 石河子：0.09 克拉玛依：0.19 塔城：0.38 阿拉泰：0.42 哈密：0.31 鄯善：0.14 吐鲁番：0.14 库尔勒：0.27 若羌：0.55 和田：0.97 喀什：0.68 阿图什：0.66 阿克苏：0.42 库车：0.28 伊犁：0.35 博乐：0.32

由图可知：可将原图分成两个子图，供游客两次游玩，然后调整边界，使结果相

I对最优。

H

G

J s BA D K t F C

E

L M

N O P R

Q

对下面的子图，可以看出，到和田的最短路径，几乎将下图所有城市连接起来，所以围绕它作局部搜索，可得路线：

乌鲁木齐→昌吉→石河子→s→t→库车→阿克苏→阿图什→喀什→和田→若羌→库尔勒→吐鲁番→乌鲁木齐（2. 13天）

P=at

=2.46*7.56*24

=386￥ （a为单位时间所需费用，如上定义）

虽然无法证明其为最优，但通过再搜索几条路线验证以及刚才围绕最短路径搜索的方法，我们有理由相信，它即使不是最优，也会是一个最优解。其路上费

最佳旅游线路的设计

21

301015

用。

对上方子图的处理有所不同，因为各个城市的最短路径与乌鲁木齐成辐射式分布，所以不能再围绕最短路径找，下面我们尝试围绕最小树做局部搜索。 利用避圈法做出最小树为： I

H

G

J s BA D K

t CF E

经过最小树附近几次搜索可得路径

乌鲁木齐→石河子→昌吉→石河子→s→t→伊市→博乐→B→克拉玛依→塔城→克拉玛依→阿勒泰→哈密→鄯善→吐鲁番→乌鲁木齐 时间为2.46天消费

P=at

=2.46*7.56*24 =446￥

5．3 分三组对新疆进行考察

在某种程度上是第二问的一个变形,我们沿袭了解决了第二个问题的思想解决了问题3;但又不完全一样,因为问题3所要达到的目的函数和问题2不一样. 我们首先作出这样的假设:1.队伍如果分成三组,则不会再分组或重新组合.2,考察队一起来到乌鲁木齐,并一起离开.3,不考虑等车时间.4,只乘汽车一种交通工具.5,由于考察比较彻底,去过的地方则不再考察.6,定义标准旅游时间t。考察时间4t。具体考察时间如下:

乌鲁木齐 19.0 昌吉 7.5 克拉玛依2.5 塔城5.25

阿勒泰10.0 哈密8.75 鄯善2 .0 吐鲁番8.25 伊宁13.5 博乐8.5 库车4.5 库尔勒11.5 阿图什4.25 喀什5.0 和田8.5 若羌7.0 石河子3.5

根据木桶效应,我们要实现的目标为考察最后到达的队伍考察所用的时间最短,即要求min{maxh(最后)};我们亦不希望看到一个队早早考察完,而另一个队还有很繁重的任务,即我们还要求min{h(最后)-h(最先)}为了简化问题,我们把第一个目标看作主要目标 (不太可能满足两个目标)做出分析.

先将地图分成3个子图,将复杂问题简单化,然后对每个子图用Dijkstra法或破圈求最小树求出近似路程最优解,然后调整边界,列出路线. 具体划分如下

最佳旅游线路的设计

22

301015

搜索结果如下(综合各方面因素，我们决定精确到小数点后一位):乌鲁木齐→昌吉(不考察) →石河子→s→博乐→伊宁→t→s→石河子(不考察) →乌鲁木齐(不考察) 45.4天

乌鲁木齐(不考察) →昌吉→克拉玛依→塔城→克拉玛依(不考察) →阿勒泰→哈密→鄯善→吐鲁番→乌鲁木齐(不考察) 46.1天

乌鲁木齐(不考察) →昌吉(不考察) →石河子(不考察) →s→t→库车→阿克苏→阿图什→喀什→和田→若羌→库尔勒→乌鲁木齐(不考察) 48.9天

结果分析:将路程忽略,把考察天数相加/3得平均考察天数为45.2天,而我们得到的结果和这个偏差不大,说明走的重复路线不多,而h(最后)-h(最先) =48.9-45.4=3.5天也是可以接受的,所以我们可以认为我们得到了近似得最优解.

5．4 “五一”线路设计问题

本题目与其他三个题目不同的地方在于要求缓解交通压力和城市旅游压力.为了完成这个目的,我们查阅了其他交通方式,最后我们发现只有在喀什,伊宁和乌鲁木齐飞往华东地区的飞机,我们不妨把喀什,伊宁和乌鲁木齐作为游客集散地.通过对城市情况的分析,我们可以看到乌鲁木齐地位远高于其他城市,所以我们假设游客来新疆必然首先来到乌鲁木齐,根据旅游世间的长短,利用我们定义的紧张系数J,求出每天在旅游景点的停留时间如下:

乌鲁木齐:3.96 昌吉1.56克拉玛依0.52 塔城1.10 阿勒泰2.08 哈密1.82 鄯善

最佳旅游线路的设计

23

301015

0.42吐鲁番1.72 石河子0.72 博乐1.78 伊宁2.82 库车0.94 阿克苏 1.26 阿图什0.88 喀什1.04 和田1.78 若羌1.46 库尔勒2.40

由于时间紧张,我们假设旅游过此地若再经过便不再旅游. 现在按照集散地将图形分区:

现在考虑的问题时,在各个区域中,怎样走才能使游客在12天的旅游中看到景区较多并浪费在路上的时间最短.在以喀什和伊宁为离开地点的线路,可看成路径最短问题,当然可以考虑利用Dijkstra算法,而以乌鲁木齐为离开地点的路线,我们可以沿用上面三问的思想.

这样我们可得路线:（综合各方面因素，我们决定精确到小数点后一位）

1. 乌鲁木齐→昌吉→石河子→s→t→库车→阿克苏→阿图什→喀什: (11.0天) 2. 乌鲁木齐→库尔勒→库车→和田→喀什 (11.6天)

3. 乌鲁木齐→吐鲁番→库尔勒→若羌→和田→喀什 (13.9)(取消) 4. 乌鲁木齐→库尔勒→若羌→和田→喀什(12.1)(取消) 5. 乌鲁木齐→吐鲁番→库尔勒→和田→喀什(12.3)(取消)

6. 乌鲁木齐→哈密→鄯善→吐鲁番→库尔勒→乌鲁木齐(11.4) 7. 乌鲁木齐→昌吉→石河子→s→博乐→伊宁(11.3)

8. 乌鲁木齐→昌吉→克拉玛依→塔城→克拉玛依→阿勒泰→哈密→乌鲁木齐(12.9)(取消)

9. 乌鲁木齐→昌吉→克拉玛依→阿勒泰→哈密→乌鲁木齐(11.4)

10. 乌鲁木齐→昌吉→克拉玛依→塔城→克拉玛依→阿勒泰→乌鲁木齐(10.5)

最佳旅游线路的设计

24

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学建模旅游问题C2(5)在线全文阅读。