（计算机应用技术专业论文）不确定环境下的旅游线路车辆配置问题.pdf

桂林工学院硕士，学位论文 摘要 旅游线路车辆配鼹问题，就是要找到在车辆配置到旅游线路上所做的最大贡献和的旅 游线路车辆配置。这个问题已经被飨予了高度重视。对旅游线路车辆配置的研究有助予旅 游监节约物流成本并提高客户满意度，对提高旅游娩的竞争力将起到重要的作用。本文原 创性地研究了在不阏的不确定环境下的最大贡献旅游线路车辆配置阀题。文中定义了一些 新的最大贡献旅游线路车辆配置概念，根据不潮的决策需求提出了若干模型，设计了混会 智能算法求解这些摸型，并给赢一些数笸试验来说骥算法的有效性。 本文把概率论号l 入到该问题中，研究了随机环境下的最大贡献旅游线路车辆配置问 题。在介缨了两种新的最大贡献旅游线路车辆配置概念之矮，本文提出了隧机期望最大贡 献旅游线路车辆配置模型、随丰凡最大贡献旅游线路车辆配置模型，将随机模拟嵌入到遗 传算法中设计了混合智能算法来求解模型，并用一个数值试验展示了算法的有效性。对乎 模糊情况，本文建立了模糊凝望最大贡献旅游线路车辆配霆模型、模糊a 。最大贡献旅游线 路车辆配置模型。根据可信性理论，在贡献值崮三焦模糊变量刻画褥假设前提下，本文分 别给出了模型的两个清晰等价形式。随后，本文给出了求解模型的混合智能算法和涯明其 有效健的数值刷子。迸一步，本文介绍了随机性和模糊性并存的不确定性的模糊随枫理论 的基本知识，提出了模糊随机期望最大贡献旅游线路车辆配置模型、模糊随机以，罗) 最大 贡献旅游线路车辆配置模型，并设计了结合模糊随机模拟和遗传算法的混合智能算法，给 出了展示算有效性的数筐侧子。最后，本文把基于概率论霸可信性理论静机会理论号| 入到 该问题中，提出了混合期望最大贡献旅游线路车辆配置模型、混合口最大贡献旅游线路车 辆配罱模型，并设计了结合混合模拟和遗传算法的混合智能舞法，给出了个数值试验展 示了算法的有效性。 总结本文的创赫点，包括以下a 个方面：( 1 ) 首次提窭了在随机环境、模糊环境、模 糊隧枧环境和混合环境下的最大贡献旅游线路攀辆配置问题的若干模型；( 2 设计了结台 不确定模拟和遗传算法的混合智熊算法，并提出了证喷箕有效性的数篷试验。 关键词：旅游线路随机模拟模猢变量模糊随机模拟 混合交璧遗传算法 桂林工学院硕士学位论文 a b s t r a c t t o u r i s tr o u t e sv e h i c l ed e l i v e r yp r o b l e mi st of i n dt h em a x i m i z a t i o nc o n t r i b u t i o nm a d eb yt h e t o u r i s tr o u t e sa n dv e h i c l ec o n f i g u r a t i o n t h i sp r o b l e mh a sb e e np a i dg r e a ta t t e n t i o n t h er e s e a r c h o ft r v d pc a nb ev e r yh e l p f u lt oc u tc o s t sa n di m p r o v et h e s a t i s f a c t i o no fc u s t o m e r s t oi m p r o v e t h ec o m p e t i t i v e n e s so ft h et o u r i s mi n d u s t r yw i l lp l a ya ni m p o r t a n tr o l e t h ed i s s e r t a t i o n o r i g i n a l l ys t u d i e st h em a x i m i z a t i o nc o n t r i b u t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r yp r o b l e mu n d e r d i f f e r e n tu n c e r t a i ne n v i r o n m e n t s i nt h ed i s s e r t a t i o n ，s o m en e wc o n c e p t so fm a x i m i z a t i o nt o u r i s t r o u t sv e h i c l ed e l i v e r ya r ed e f i n e d ，s e v e r a lm o d e l sa c c o r d i n gt od i f f e r e n td e c i s i o nr e q u i r e m e n t s a r ep r o p o s e d ，s o m eh y b r i di n t e l l i g e n ta l g o r i t h m sa r ed e s i g n e df o rs o l v i n gt h em o d e l s ，a n ds o m e n u m e r i c a le x p e r i m e n t sa r ep r e s e n t e dt os h o wt h ee f f e c t i v e n e s so ft h ea l g o r i t h m s b yi n t r o d u c i n gt h ep r o b a b i l i t yt h ep r o b l e m ，t h ed i s s e r t a t i o ns t u d i e st h em a x i m i z a t i o n c o n t r i b u t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r yp r o b l e mi ns t o c h a s t i ce n v i r o n m e n t f o l l o w i n gt h e i n t r o d u c t i o no ft w on e wc o n c e p t so fm a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r y , t w ot y p e so f m o d e l s ：s t o c h a s t i ce x p e c t e dm a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r ym o d e l ，s t o c h a s t i ca - m a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r ym o d e la r ep r o p o s e d i no r d e rt os o l v et h em o d e l s ， s t o c h a s t i cs i m u l a t i o ni se m b e d d e di n t og e n e t i ca l g o r i t h mt op r o d u c eah y b r i di n t e l l i g e n t a l g o r i t h m t h ee f f e c t i v e n e s so ft h ea l g o r i t h mi si l l u s t r a t e db yan u m e r i c a le x p e r i m e n t f o rt h e f u z z yc a s e ，t h ed i s s e r t a t i o nf o r m u l a t e sf u z z ye x p e c t e dm a x i m i z a t i o nt o u r i s tr o u t e s v e h i c l e d e l i v e r ym o d e l ，f u z z y 口m a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r ym o d e l b a s e do nt h e c r e d i b i l i t yt h e o r y , t h ec r i s pe q u i v a l e n t so f t h em o d e l sa r e p r e s e n t e da s s u m i n gt h a t t h e c o n t r i b u t i o n sa r ec h a r a c t e r i z e db yt r i a n g u l a rf u z z yv a r i a b l e s ah y b r i di n t e l l i g e n ta l g o r i t h mi s d e s i g n e dt os o l v e t h em o d e l s ，w h i c hi sp r o v e dt o b ee f f i c i e n tb yan u m e r i c a le x a m p l e f u r t h e r m o r e ，t h eb a s i ck n o w l e d g eo ft h ef u z z yr a n d o mt h e o r yi si n t r o d u c e df o rd e a l i n gw i t ht h e m i x e du n c e r t a i n t yo fr a n d o m n e s sa n df u z z y n e s s f u z z yr a n d o me x p e c t e dm a x i m i z a t i o nt o u r i s t r o u t e sv e h i c l ed e l i v e r ym o d e l ，f u z z y r a n d o m ，卢) - m a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r y m o d e la r eb u i l t ah y b r i di n t e l l i g e n ta l g o r i t h mi n t e g r a t i n gf u z z yr a n d o ms i m u l a t i o na n dg e n e t i c a l g o r i t h mi sp r o d u c e da n dan u m e r i c a le x p e r i m e n ti sg i v e nt os h o wt h a tt h ea l g o r i t h mi s e f f e c t i v e n e s s f i n a l l y , c h a n c et h e o r yb a s e do np r o b a b i l i t yt h e o r ya n dc r e d i b i l i t yt h e o r yi s i n t r d u c e di n t ot h i sp r o b l e m h y b r i de x p e c t e dm a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r ym o d e l a n dh y b r i d 口- m a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l ed e l i v e r ym o d e la r em a d e h y b r i di n t e l l i g e n t a l g o r i t h m sc o m b i n i n gh y b r i ds i m u l a t i o n a n dg e n e t i ca l g o r i t h ma r ed e s i g n e dt os o l v et h e s e m o d e l s i nt h ee n d ，n u m e r i c a le x a m p l e sa r eg i v e nt ov a l i d a t et h ea l g o r i t h m s i nc o n c l u s i o n ，t h i sd i s s e r t a t i o nc o n t r i b u t e st ot h et o u r i s tr o u t e sv e h i c l ed e l i v e r yp r o b l e mi 1 1 桂林工学院硕士学位论文 ! ! ! ! 竺黑= ! ! i i i i iii l l l l liiiii i i i i 一i h i = i ： t h ef o l l o w i n ga s p e c t s ：( 1 ) s e v e r a lt y p e so fm o d e l sf o rt h em a x i m i z a t i o nt o u r i s tr o u t e sv e h i c l e d e l i v e r yp r o b l e mu n d e rs t o c h a s t i c ，f u z z y , f u z z yr a n d o ma n dh y b r i de n v i r o n m e n t s a l eb u i l tf o rt h e f i r s tt i m e ；( 2 ) h y b r i di n t e l l i g e n ta l g o r i t h m si n t e g r a t i n gu n c e r t a i ns i m u l a t i o n a n dg e n e t i c a l g o r i t h ma r ed e s i g n e d et os o l v et h em o d e l sa n ds o m en u m e e r i c a le x p e r i m e n t sa r ep r e s e n t e dt o i l l u s t r a t et h ee f f e c t i v e n e s so ft h ea l g o r i t h m s k e yw o r d s ：t o u r i s tr o u t e r a n d o ms i m u l a t i o n f u z z yv a r i a b l e f u z z yr a n d o ms i m u l a t i o n h y b r i dv a r i a b l eg e n e t i ca l g o r i t h m 鞋l 桂林工学院硕士学位论文 主要符号对照表 亭、r 、p 随机变量、模糊变量、模糊随机变量、混合变量 p r概率测度 c r可信性测度 c h机会测度 e期望值算子 ( 0 ，p ( a ) ，c r ) 可信性空间 尺实数集 桂林工学院硕士学位论文 研究生学位论文独创性声明和版权使用授权说明 独创性声明 本人声明：所呈交的论文是我个人在林亮教授指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人 已经发表或撰写过的研究成果，也不包含为获得桂林工学院或其它教育机构的学位 或证书而使用过的材料。对论文的完成提供过帮助的有关人员已在论文中作了明确 的说明并致以了谢意。 学位论文作者( 签字) ： 签字日期： 版权使用授权说明 本人完全了解桂林工学院关于收集、保存、使用学位论文的规定，即：，按照学 校要求提交学位论文的印刷本和电子版本：学校有权保存学位论文的印刷本和电子 版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手 段保存论文：在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。( 保 密论文在解密后遵守此规定) 学位论文作者( 签字) ： 指导教师签字： 签字日期： 监 桂林工学院硕士学位论文 第1 章引言 i 1 选题背景及其意义 随着市场经济的迅速发展及全球化进程的j i i i i ，市场竞争羽益激烈的今天，越来越 多的旅行社更加重视旅游车辆配置在旅游线路上对提高旅行社竞争力的作用。关于旅游 线路的概念，孙伶俐【1 1 提出了两种不同的观点，一种观点认为旅游产品是一个整体的概 念，是旅游者在旅游过稚中的综合感受。它的实现条件之一就是旅游线路，一条旅游线 路就是一件旅游产品，任何节点、景点、服务方式等发生变化，旅游产品都会发生变化。 另一种观点认为旅游线路是旅游产品的生产线，而不是一种旅游产品。在同一条旅游线 路上可以接待若干个旅游者，为若干入提供旅游经历，也就是说生产了若予个旅游产品。 本文认同第一种观点，认为旅游线路是旅行社旅游产品的表现形式。旅游线路的经营是 旅行社经营的基础。 旅游线路是一种旅游产品。企业竞争是以产品为媒奔的，圜内外旅行社的竞争实质 是旅游线路的竞争。如何提高旅游线路的竞争呢? 目前我国旅行社旅游线路的经营存在 着很多问题。主要表现在旅游线路大同小异、缺乏特色、更新缓慢，只能靠价格来吸引 旅游者，这使旅行社陷入价格战鳃漩涡不能自拔；旅游线路的设计不合理、不以旅客为 中心、旅游线路营销效果不理想等。旅游线路的无差异性、设计不合理的根源是缺乏对 市场需求的调查研究。旅游线路设计不合理、更新缓慢、不以旅客为中心也是缺乏顾客 营销理念。旅游线路的嚣销的曩的就在予创造可赢利的价值。显然，要想旅游线路的营 销获得更多利润，提高旅游线路的竞争力，就需要合理的设计旅游线路，因此，目前有 一些学者致力于这方面的研究。鲁瑾【2 l 提出旅游线路专营的经营模型，孙艳红1 3 l 从旅游 系统理论、行为地理说和旅游经济学的角度对旅行社旅游线路设计定利进行了研究，提 出了旅行社旅游线路定制决策模型，吴凯和刘啸等1 5 】把运筹学的方法引入旅游研究， 探讨旅游线路的优化设计，谭彩荷f 6 l 利用旅游线路设计的基本原理和原则分孝斥实例，周 莉i 1 分析旅游线路设计与开发过程中存在的问题，楚义芳嘲研究了开发旅游线路设计成 功的五大基本要素等等。由于学者们对旅游线路设计的理论框架有所不同，所以设计出 来的旅游线路也有所不同，但是，旅游线路的设计大致可以分为四个阶段。首先，要确 定目标市场( 旅客群) 的成本因子，它在总体上决定了旅游线路的性质和类型。其次， 根据旅客的类型和期望确定组成为线路内容的旅游吸引物的基本空间格局，旅游吸引物 桂林工学院硕士学位论文 对应旅游价值必须用量亿的表示出来。第三，结合前两阶段的背景材料对相关的旅游基 础设施和专用设施进行分析，设计出若干可供选择的线路。第四，选择最优的旅游线路 ( 可以有几条) 。其中，第三阶段的工作最富经验性( 技术性) ，设计中必须对第二阶段 给出的基本空间格局不断进行调整，以形成新的，带综合意义的空问格局。旅游线路的 设计好坏，旨在吸引旅客。而对旅行社来说，如何在旅游线路上获得更高的利润方是旅 行社经营的目的。在尽量降低成本的基础上，不断挖掘旅游线路的价值才是提高盈利的 最壹接、最有效的途径，也是增强旅游线路核心竟争力的关键所在。旅行社应该要想方 设法提高旅游线路的产品价值，提高旅游线路的形象和工作人员的服务品位，始终为旅 客着想，不断降低旅客的体力、精力和时间成本。一个重要方面就是交通工具在旅游线 路上的配置。合理的配置交通工具可使旅游线路的成本降低，提高旅游线路的竞争力， 使旅行社获得更多的利润。比如，考虑下面的一个问题：假设某旅行社拥有若干种类车 辆数量和若干条旅游线路，我们需要将这些车辆配置到旅游线路上，每辆车只能在一条 旅游线路上使震，著且在旅游线路上的贡献值已知( 根据经验性得到) 。悉虽每类车辆的 数量是已知的。作为决策者，我们的目标是制定最合理的配置方案使这些军辆在旅游线 路上得到充分利用。使旅行社获得最大的利润。 在现蜜世赛孛，各种各样的不确定因素存在于几乎所有的实际问题孛。无论是在叁 然科学领域还是在工程技术领域，甚至在社会科学领域，各种客观的或者人为的不确定 因素都因对具体问题的显著影响而为人们所重视。越来越多的学者把精力从研究确定性 闻题转移到考察和分析阀题中的不确定性上。焉些学者已经不满足于研究传统的随机 现象，而把注意力放在诸如模糊性、粗糙性，多重不确定性等其他不确定性的研究上。 将不确定性分析纳入对实际问题的研究中，已经成为目前各个领域科学研究的一个趋势。 由于旅游线路豹车辆配置对旅行社的经营在竞争中起到重要的作用。因此对这个闯题中 的不确定性因素进行分析研究是很有必要的。比如上文所举的例子中，现实的情况是车 辆在旅游线路上的贡献值并不是确定的，它与车辆的状态、统计数据、人的经验等等不 确定因素都有关系。那么用确定豹量去衡量这个贡献值显然是不能让入满意的。最传统 最早为人们所接受的一类不确定形式随机性，概率论是研究这类不确定性的数学分支， 我们可以融然的认为车辆配置在旅游线路上的贡献值可以用随机变量来刻域。但是，对 于缺乏或遗失数据的情况，概率论无能为力，我们必须考虑闻题中存在的模糊性。而在 更复杂的情况中，也许我们具有一定的经验数据，但是不够完备，这时可能存在随机性 2 桂林工学院硕士学位论文 和模糊性并存的混合不确定性。鉴于实际问题中的不确定性真实存在，研究不确定情形 下的车辆配置问题一定具有广阔的应用前景。而目前对不确定环境下的车辆在旅游线路 上配置问题的研究是空白的。也使得本文具有一定的理论价值。 目前，对于旅游线路车辆配置问题的研究主要是在确定的环境下。常朝稳【9 1 等研究 了约束规划的旅游多车辆行程路线，孟爱国 1 0 1 等对遗传算法作了改进，进行求解旅游线 路选择问题，这些旅游线路的车辆配置在确定情况下有着很好的效果。但是它们无法解 决不确定环境下的旅游线路车辆配置问题。因此，我们必须开辟研究此问题的新途径。 由于上世纪计算机的快速发展，遗传算法、模拟退火、人工神经元网络等各种启发式算 法逐渐为人们所青睐，并展现了传统算法无法比拟的优势，其效果是依赖于具体问题的。 对于具体的实际问题，由于其目标函数和可行域的独特性，不加分析地硬套某种启发式 算法，一般是很难达到预期的求解效果的。因此，成功应用启发式算法，就必须对算法 进行一定的改进，使其符合被求解问题的具体情况，有效地求解问题，这是启发式算法 运用的一大难题。本文根据不确定环境下的旅游线路车辆配置问题的具体分析，设计了 合适的有效的混合智能算法来对其求解。 本文将首次考虑不确定环境下的旅游线路车辆配置问题，针对随机性、模糊性和随 机性与模糊性并存的不确定性，并考虑到不同的决策准则，提出了二类不确定模型。结 合不确定模拟与遗传算法，本文设计了对不确定环境下旅游线路车辆配置问题有效求解 的混合智能算法，并通过几个数值试验对算法求解的有效性进行了说明。 1 2 国内外研究动向 到目前为止，对旅游线路车辆配置问题的研究主要还是在于对确定型问题寻求更为 有效的算法，而对于不确定环境下的旅游线路车辆配置的研究还是一片空白。 现实世界中遍布着各种各样的不确定性，人们在探求事物规律，解决实际问题的过 程中，不可避免地需要面对这些不确定性。忽视不确定性的存在，无论是科学研究还是 技术发明都必然一定程度地偏离实际，达不到很好地解决问题的效果。因此，在很早之 前，人们就已经主动地寻求方法去处理客观的或者人为的不确定性。最早为人们所认识 并研究的，是人们最为熟悉的随机现象。早在几百年前，就已经有人认识这种不确定性， 并对其有过基本的描述。而到了上个世纪三十年代之后，作为专门处理随机性的数学分 支概率论逐渐完善起来。概率论的完善和发展，使其被成功的应用于包括基础科学、 工程技术、社会科学在内的几乎一切领域。 然而，概率论并不能解释和处理所有的不确定性。由于事物的一些性质缺乏或者丢 3 桂林工学院硕士学位论文 失经验数据，概率论显的无能为力；而诸如对距离、重量、位置等的估计，用随机变量 描述这些量也并不恰当。这种与随机性不同的不确定性带有主观因素，被称为模糊性。 早在1 9 6 5 年z a d e h 1 1 i 最早提出了模糊集的概念，而后几十年模糊集理论在这个概念上迅 速发展起来，成为处理模糊性的有力工具。1 9 7 5 年，k a u f m a n n 1 2 l 首先提出了模糊变量的 概念。1 9 7 8 年z a d e h t l 3 l 引入了可能性理论。在n a h m i a s t l 4 l 关于可能性测度的三条公理的 基础上，l i u t l 5j 于2 0 0 2 年给出了关于乘积可能性测度的第四条公理，为我们处理模糊性 和解决存在模糊现象的实际问题提供了强大的理论支持。 对于不确定性的研究，人们并没有只停留在单一的不确定性上，对于多重不确定性 并存的复杂情况，其研究也有了一定的发展。对于不确定性的研究，l i u t l 6 】在他的著作里， 做了详细地、系统地阐述，并提出了不确定理论的概念。不确定理论作为研究随机现象、 模糊现象、粗糙现象以及多重不确定现象的数学分支，不仅成为不确定性研究的理论基 础，而且与数学规划相结合形成了不确定规划 1 7 , 1 9 , 2 0 1 ，为解决实际问题提供了强大的工具。 在不确定规划中，由于存在着一些不确定函数，其求解尤其困难。数学规划中的传 统方法对于求解不确定规划，往往是无能为力的。l i u 1 8 l 在他的著作中，具体地介绍了 多种不确定模拟方法，使得求解各种环境下的不确定函数成为可能。而几十年来，包括 遗传算法、人工神经元网络、模拟退火、禁忌搜索、蚂蚁算法等在内的启发式算法的层 出不穷与快速发展，使得传统算法的不足得到了弥补。 1 3 本文的结构安排 本文首次提出并探讨了不确定环境下的旅游线路车辆配置问题，主要对随机、模糊、 模糊随机、混合四种不确定环境下的最大贡献旅游线路车辆配置问题进行了建模，并设 计了有效求解此问题的混合智能算法。文章的结构安排如下： 第二章我们将对不确定环境下的旅游线路车辆配置问题做基本描述。 第三章研究了随机环境中的旅游线路车辆配置问题，根据不同的决策准则提出了两 个在随机环境下的最大贡献旅游线路车辆配置概念，并且提出了求解这些最大贡献旅游 线路车辆配置的模型。随后，我们介绍了求解含有随机变量的不确定函数的随机模拟， 并详细阐述了针对旅游线路车辆配置问题设计的遗传算法，进一步，我们将二者结合设 4 桂林工学院硕士学位论文 计了混合智能算法来求解前面提出的两个模型。最后，我们给出了组数值例子，说明 算法的有效性。 第四章考察了模糊环境下的旅游线路车辆配置问题。首先我们简要介绍可信性理论 的基本知识，为后面的建模奠定基础。随后，我们同样根据不同的决策准则提出两个在 模糊环境下最大贡献旅游线路车辆配置的概念和求解这些旅游线路车辆配置的模型。接 着，在一定的假设前提下，我们运用可信性理论的知识，分别给出了上述两个模型的清 晰等价形式。对于一般情况，我们给出了模糊模拟来估计不确定函数，并嵌入遗传算法 构成混合智能算法。在本章的最后，我们给出一个数值试验说明算法的运用。 第五章针对随机性和模糊性并存的旅游线路车辆配置问题进行探讨。为了建立此情 况下的模型，首先我们引入了模糊随机理论，给出两个在模糊随机环境下的最大贡献旅 游线路车辆配置的新概念，根据不同的决策需求，提出了两类模型。结合模糊随机模拟 和遗传算法，我们设计了混合智能算法求解模型。算法的有效性在本章最后被一个数值 试验证明。 第六章在上一章的随机性和模糊性并存的情况下，我们做了进一步的研究，引入了 基于概率论和可信性理论的机会理论，给出了两个在混合环境下的最大贡献旅游线路车 辆配置的新概念，根据不同的决策需求，提出两种模型，将混合模拟嵌入到遗传算法中， 我们设计了混合智能算法来求解模型。最后，给出了一组数值试验，验证算法的有效性。 最后，在结论部分我们总结了本文的主要工作，并对今后可以继续开展的工作进行 了展望。 5 桂林工学院硕士学位论文 第2 章旅游线路车辆配置问题的基本描述， 旅游线路车辆配置问题就是在确定的旅游线路上配置车辆，由于各种车辆类型功能 不同，配鼹到旅游线路上所起的作用也不同，我们将每类车辆配置到各旅游线路上得到 一个评 舂值( 贡献值) ，对旅行社来说，把车辆合理的配置到旅游线路上，充分利用车辆 的作用，可以提高旅游线路的竞争力，为旅行社赢得更大的利润。因此，根据其决策目 标不同， 建立了不同的最大利润旅游线路车辆配翌问题。 在旅行社的日常工作中，经常会遇到将车辆配置到各个旅游线路的问题。如何使配 置达到最优，发挥车辆服务的最大效能，是旅行社面临的一个复杂问题。假设某旅行社 有m 类车辆和n 类旅游线路，我们考虑把每一种车辆配置到不同的旅游线路上评信出一 个贡献值( 即权重值) ，每个贡献值乘以每一种类型车辆的数量，再将这些值全部相加， 就得到所有类型车辆配罱到所有的旅游线路上做出的贡献总和： ( x ，妨一善善嘞 使这个贡献总和为最大的配置方法就是旅游线路车辆配置的最优方法。 为了建立旅游线路车辆配置问题的模型，使用以下的指标，参数和决策变量： i 一1 , 2 ，m ：表示第f 种类型车辆； j = 1 ，2 ，l ：表示第，类型旅游线路； q ，：表示车辆类型f 配置到类型旅游线路做出的贡献大小； ：表示车辆类型i 配置到，类型旅游线路的车辆数量；艺谚，f 一1 ，2 ，小，其中6 ： 为 整数； ) ，i ：表示第f 类型车辆的总数量。 现实世界中，车辆配置到旅游线路上所评估出的贡献值往往带有一定的不确定性， 这便使得我们必须对不确定环境下的旅游线路车辆配置问题进行研究。这里，我们主要 是通过贡献值设为不确定变量，进而对不确定环境下旅游线路车辆配置进行考察。我们 用岛取代魄来表示贡献值。岛在不网的不确定环境下代表不同的不确定变量：在随机环 境下，其代表随机变量；在模糊环境下，其代表模糊变量；而在随机和模糊并存的环境 6 桂林工学院硕士学位论文 下，其可以表示模糊随机变量和混合变量。我们记 亭一 岛ii 一1 , 2 ，m ；j l 2 ，l 】- ，x - i x fii - 1 ，2 ，m ；j = 1 2 ，l 约束条件为： 薹z f 。y j ，j q ，：) ；f ，j f - _ _ l ，2 ，l ，f - 1 ，：! ，。，所 丽旅游线路车辆配置x 的贡献值和被表示为： 厂勤2 茹善岛 旅游线路车辆配置问题就是要找到使得f ( x ，势最大豹旅游线路车辆配置闯题。 本章对于不确定环境下的旅游线路车辆配置问题作了简单的介绍，为后面建立不同 环境下的模型奠定了基础。 7 桂林工学院硕士学位论文 第3 章随机环境下的旅游线路车辆配置问题 在现实世界中，到处存在着各种各样的不确定性。无论是客观的还是人为的，我们 都不可否认这些不确定性的存在，他们随着人类社会的进步，越来越被人们重视。最早 被人们认谈的一种不确定性就是随机性。虽然人类对他的思索可以追溯到a 西年前，但 是对于随机性的研究真正成为一个科学分支，是在1 9 3 3 年k o l m o g o r o f f 建立了概率论的 公理化体系之后。几十年之后的今天，概率论已经有了长足的发展，其内容被极大地充 实，它已经成为一个相当成熟的数学分支。丽黑，在科学和工程的各个领域中，概率论 都有广泛的应用。正是因为它能有效地处理实际问题中存在的随机现象，概率论才有着 不衰的生命力。由于旅游线路车辆配置问题的研究成果对旅行社经营在旅游业竞争中立 子不败之地起到关键作用。因此，对随机环境下的旅游线路车辆配置的研究是很有必要 的。在本章中，我们用随机变量刻画贡献值，每个岛都表示一个随机变量。我们首次 将概率论弓| 入到旅游线路车辆配置阕题中，探究了随机环境下的旅游线路车辆配置问题。 根据不同决策需求给出了二个模型，并设计了混合智能算法来求解这些模型，在最后还 给出一个数值例子来说明算法的有效性。 3 。随机环境下旅游线路车辆配置问题的模型 3 1 1 随机期望最大贡献旅游线路车辆配置模型 我们知道，对于含有不确定函数的优化问题，尤其是目标函数是不确定函数的情况， 我们不能童接对不确定涵数进行优化。比如在旅游线路车辆配置问题孛，车辆配置到旅 游线路的效能，即贡献值就是随机变量。我们无法直接对随机变量进行极大化或者极小 化。在这种情况下，一个直观的想法是对不确定暖标函数的期望值进行优化。在本问题 中，决策者很自然地想要找到一个车辆配置方案，并满足它的贡献值的总和期望值最大。 在给出模型之前，我们首先定义具有这样性质的旅游线路车辆配置： 定义3 1 一个旅游线路车辆配置x 被称为随机期塑最大贡献旅游线路车辆配霹，如果对 予满足约束条件 嘞一以，红，f 一协- ，删 j - l 的任意旅游线路车辆配鬣x 都有 e f ，亭) 】苫e f ，宇) 】， s 桂林工学院硕士学位论文 其中，e f ( x ，亭) 】叫做期望最大贡献值。为了求解随机期望最大旅游线路车辆配置，我们 引入期望值模型( e v m ) 。期望值模型的本质是在满足期望约束的前提下最优化期望目标 函数，与随机环境下的旅游线路车辆配置问题相结合，我们提出了如下的随机期望最大 贡献旅游线路车辆配置模型： m a 她嚼善毛】 荟嘞嘶江m ，朋 x , j 苫6 f ，i 一1 2 ，m ；j = l 2 ，n ( 3 1 ) 如果每一个岛的期望值有限，那么根据概率论的结论，我们可以将模型( 3 - 1 ) 转化为下 面的清晰等价形势： m a x 再善e 【岛k 酗5 咒, i - - 孙。，肌 x o 红，i 一1 ，2 ，m ；j = 1 ，2 ，刀 3 1 2 随机口一最大化旅游线路车辆配置模型 ( 3 2 ) 在有些时候，决策者也许对期望值模型的结果并不满意，这是因为期望值虽然在一 定程度上刻画了随机变量的取值性质，但由于随机性的存在，随机变量的取值可能会远 离期望值，这对决策者来说具有一定的决策风险。因此，很多决策者倾向于在一定的置 信水平下满足约束条件，并优化目标函数的贡献值。这是一种机会约束规划的思想。在 1 9 5 9 年，c h a r n e s 和c o o p e r t 2 1 i 首先提出了机会约束规划模型( c c p ) 。之后l i u t v a a l 等学 者对其进行了发展。c h a m e s 和c o o p e r l 2 1 】的模型中只考虑了随机约束，而l i u 1 7 1 将机会 约束规划推广到同时考虑随机约束和随机目标。我们在本节将机会约束规划的思想引入 到随机环境下的旅游线路车辆配置问题建模中，建立了随机口最大贡献旅游线路车辆配 置模型。在提出模型之前，我们给出随机口最大贡献旅游线路车辆配置的定义： 定义3 2 一个旅游线路车辆配置x 被称为随机口最大贞献旅游线路车辆配置，如果对于 9 桂林工学院硕士学位论文 满足约束条件 酗叫t ，嘶i - 1 , 2 , - , m 的任意旅游线路车辆配置x 都有 m a x tjp r f ( x ，亭) r ) a ) 之m a x tip r ，o ，亭) 丁口， 其中，口是一个预先给定的置信水平，这个最大的r 叫做旅游线路车辆配置的口贡献值。 为了求解随机a 最大化旅游线路车辆配置，我们运用机会约束规划的思想，建立如 下的随机口最大贡献旅游线路车辆配置模型： m a x t s j p r 骞姜毛嘞螂口 善。z , i - 啦，朋 嘞之岛，i 一1 2 ，m ；j - 1 , 2 ，肛 其中口是由决策者预先给定的置信水平。 3 2 混合智能算法 ( 3 3 ) 由于随机环境下的旅游线路车辆配置问题的目标函数是不确定的，我们需要寻求其 他方法进行求解。本节我们将随机模拟和遗传算法结合起来，设计了针对随机环境下的 旅游线路车辆配置问题的混合智能算法。 3 2 1随机模拟 对于模型中出现的不确定函数，我们用随机模拟来估计它们的值。方便起见，我们 把 亭表示成亭一( 袅，岛，如) ，其中m 是贡献值的数目。 随机环境下旅游线路车辆配置问题中出现的第一个不确定函数是： u l ：工- e f o ，亭) 】 根据概率论中的大数定律，我们可以通过从概率空间次选取样本并求函数值， 1 0 桂林工学院硕士学位论文 然后对其取平均值来估计上述函数中的期望值。模拟过程如下： 步骤1 令u 。o ) 一0 。 步骤2 根据概率测度p r 从q 中生成0 9 一( l ，0 9 2 ，0 9 | l f ) 。 步骤3 u 。o ) - 【， ) + f ( x ，亭( ) ) 。 步骤4 将步骤2 和步骤3 重复次，其中是个足够大的数。 步骤5 u 。o ) _ u 。o ) 。 第二个需要模拟的不确定函数具有如下形势： u 2 ：工呻m a x 仃ip r f o ，亭) 2r 苫口 对于这个函数的模拟，我们可以从概率空间次选取样本并求函数值，然后找到 其中第大的值作为这个函数的估计，其中是( 1 一a ) n 的整数部分。具体的模拟过程 如下： 步骤1 根据概率p r 从q 中生成0 9 1 ，：，0 3 n ，其中是一个足够大的数。 步骤2 令，i f ( x ，善) ，其中皇= 亭( q ) ，f 一1 2 ，n 。 步骤3 令 r 为( 1 一a w 的整数部分。 步骤4 返回 厂l ，f 2 ，) 中的第大的值。 3 2 2 遗传算法 由于传统算法对于求解不确定环境下的旅游线路车辆配置问题并不适合，我们必须 另辟蹊经，运用启发式算法来求解最优旅游线路车辆配置。本节中我们将介绍一个针对 不确定环境下旅游线路车辆配置问题设计的遗传算法。遗传算法是一种基于自然选择和 生物进化的随机搜索优化问题最优解的启发式算法，它最早由h o l l a n d t 2 2 1 于1 9 7 5 年提出。 遗传算法不仅不要求对问题进行深入的数学分析，而且还能跳出局部最优解而找到全局 最优解，其优势是传统算法无法比拟的。正是由于其高效率的优势，遗传算法被成功应 用于求解复杂的和不确定的优化问题2 4 t 2 5 1 以及一些诸如机器学习等工程技术领域 2 6 , 2 7 , 2 8 1 。遗传算法的机理是将问题的解设定为或者转化为“染色体”，并通过选择、交 叉、变异等过程来模拟生物界的进化过程，并最终得到对应于最优解的最优染色体。设 计一个遗传算法，必须要设计一个染色体的表示结构，使得每一个解都有染色体来表示 桂林工学院硕士学位论文 它。在设计好表示结构之后，首先要生成一定数量染色体的种群作为初始种群，然后通 过一定的评价函数如目标函数等对染色体进行评定，并得到每个染色体的适应度。适应 度反映了染色体的优劣性。然后，根据一定的选择机制( 如轮盘赌的方式) ，选择染色体、 以构成新的种群。在得到新种群之后，人们必须设计交叉和变异操作来对种群中的染色 体进行更新。交叉和变异，来源于对生物界遗传行为的模仿，前者可以对父代染色体保 留优点摒弃弱点并增加染色体的多样性，而后者正是跳出局部最优解而寻求全局最优解 的保证。至此，新一代的种群已经产生，重复上述过程一定次数，可以得到代表最优解 的最优染色体。从遗传算法的上述描述中，我们不难看出它具有对问题无需深入数学分 析和获得全局最优解的优点，然而对于不同的问题，使用遗传算法是需要设计适应于具 体问题的选择，交叉和变异操作以及评价函数等，这是遗传算法应用的一大难点。 针对旅游线路车辆配置问题，我们设计了针对不确定环境下旅游线路车辆配置问题 的遗传算法。 3 2 2 1 表示结构 最优化问题的解有两种表示方法：二进制向量或浮点向量。使用二进制向量作为一 个染色体来表示决策变量的真实值，向量的长度依赖于要求的精度，但使用二进制代码 的必要性已经受到了一些批评。在求解复杂优化问题时，二进制向量表示结构有时不太 方便。 另一种表示方法是用浮点向量，每一个染色体有一个浮点向量表示，其长度与解向 量相同。用向量z o 。，j c ：，x 。) 表示最优解问题的解，其中一是维数。则相应的染色体 是vt o l ，工2 ，x ) 。 在随机环境下的旅游线路车辆配置问题中，我们用第二种表示方法来表示问题的解， 相应的染色体也就得出了，即染色体v - “，工：，z 肼) 。 3 2 2 2染色体初始化 对于每一个染色体y 在约束条件( 3 1 ) 中，我们可以得出可行集中的一个内点，一记 为。我们定义一个足够大的数m ，以保证遗传操作遍及整个可行集。当然m 的选取依 赖于不同的决策问题。在尺m 中，首先随机选择一个方向d ，如果+ m d 满足不等式 约束，则将v i l lv o + m d 作为一个染色体，否则，置m 为0 到m 之间的随机数，直到 v o + 肘记可行为止。由于是内点，所以在有限步内，总是可以找到满足不等式约束的 1 2 桂林工学院硕士学位论文 =ms一l =m = i ! ! !