摘 要

随着我国经济的快速发展，旅游业在以更加迅猛的速度前进,但由于旅游公司众多，旅游公司竞争激烈，使得游客分布不均匀、旅游市场碎片化，进一步导致中小型旅游公司游客不足产生亏损。另外旅游公司之间信息的不公开使得旅游市场碎片化难以进行整合，而互联网的发展为旅游线路资源整合的提供了可能。本文拟在互联网环境中，将旅游线路看作可交易的商品，构建一个旅游资源中间商平台，旅游中间商拥有旅游商品，中间商根据旅游公司需求进行旅游商品的分配，进而解决旅游公司因游客不足产生的亏损。本文从旅游中间商的角度出发将旅游线路分配问题转化为组合拍卖问题，并采用两种不同的算法来解决组合拍卖中的胜者决定问题，即组合拍卖中商品分配问题，从而最大化旅游资源中间商的收益。本文的主要研究内容如下：

1）构建旅游资源市场模型，包括旅游资源交易者模型和旅游资源中间商模型。将旅游资源分配问题转化为商品交易问题，并在组合拍卖的环境下进行求解。

2）采用贪心算法和微生物遗传算法对胜者决定问题进行求解。贪心算法每次分配平均价格最低的投标，微生物遗传算法通过不断地迭代搜索更好的投标分配序列。

3）对上述的两种解决方法进行了评估分析，本文从分配率、单位支付金额和总成本，三个方面对旅游资源分配算法进行了评估和分析。实验发现贪心算法在单位支付金额上表现的很好，但资源分配率上表现不佳。微生物遗传算法解决了第一种算法分配率不高的问题，同时在单位支付金额和总成本上有着不错的表现。

关键字：组合拍卖；胜者决定；旅游资源；贪心算法；微生物遗传算法

Abstract

With the rapid development of China’s economy, tourism is advancing at a more rapid speed. But there are numerous tourism companies competing fiercely, which makes the distribution of tourists uneven. This has led to the loss of small and medium-sized tourism companies due to inadequate tourists. In addition, the non-disclosure information between tourism companies makes it difficult to integrate fragment of tourism market, and the development of the Internet provides the possibility of tourism route resource integration. In this paper, tourist routes are regarded as tradable goods in an Internet environment and a tourism resource middleman platform is constructed. The tourism resource middleman owns tourism goods and the middleman allocate tourism goods according to the needs of the tourism companies, thus solving the loss of tourism companies due to the inadequate tourists. This paper tackle tourism route allocation problem as combinatorial auction from the perspective of tourism resource middleman, and two different algorithms are used to solve the winner determination in the combinatorial auction, namely the commodities allocation problem in combinatorial auction, so as to maximize the income of the tourism resource middleman. The main research of this paper are as follows:

1) We construct a tourism resources market model, including a tourism resource trader model and a tourism resource middleman model. Tourism resource allocation problem is transformed into commodity transaction problem which is the solved in combinatorial auction environment.

2) Greedy algorithm and microbial genetic algorithm are designed to solve the winner determination problem. The greedy algorithm bids the lowest average price for each round of allocation while the microbial genetic algorithm continuously searches for better bid allocation sequences.

3) The above two solutions are evaluated and analyzed. Then we evaluate and analyze the distribution algorithm of tourism resources from three aspects: distribution rate, unit payment amount and total cost. The experiment shows that the greedy algorithm performed well on the unit payment amount, but did not perform well on the resource allocation rate. The microbial genetic algorithm solves the problem of the low distribution rate of the first strategy, and has a good performance in the unit payment amount and total cost.

keywords：Combinatorial Auction; Winner Determination; Tourism Resource;

Greedy Algorithm; Microbial Genetic Algorithm

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 国内外研究现状 2

1.3 主要工作和技术线路 3

1.4 论文结构 4

第2章 模型构建 6

2.1 问题描述 6

2.2 基于组合拍卖的旅游资源交易模型 6

2.3 评估标准 8

2.4 小结 8

第3章 基于贪心算法的旅游资源分配 9

3.1 贪心算法 9

3.2 实验分析 9

3.2.1 参数设置 9

3.2.2 实验结果 11

3.2.3 参数对分配结果的影响 12

3.3 小结 15

第4章 基于微生物遗传算法的旅游资源分配 16

4.1 微生物遗传算法 16

4.2 实验分析 17

4.2.1 参数设置 17

4.2.2 实验结果 19

4.2.3 参数对分配结果的影响 20

4.3 与贪心算法的对比分析 25

4.4 小结 27

第5章 总结与展望 28

5.1 总结 28

5.2 研究展望 28

参考文献 30

致 谢 33

第1章 绪论

1.1 研究背景

根据国家旅游数据中心统计，2017年，国内旅游市场高速增长，入出境市场平稳发展，供给侧结构性改革成效明显。国内旅游人数50.01亿人次，比上年同期增长12.8%；入出境旅游总人数2.7亿人次，同比增长3.7%；全年实现旅游总收入5.40万亿元，增长15.1%。初步测算，全年全国旅游业对GDP的综合贡献为9.13万亿元，占GDP总量的11.04%。旅游直接就业2825万人，旅游直接和间接就业7990万人，占全国就业总人口的10.28%^[1]。由此可见旅游业对我国经济发展影响重大，虽然国内目前拥有较大的旅游市场，但由于旅游公司众多，旅游公司竞争激烈，使得游客分布不均匀、旅游市场碎片化，进一步导致中小型旅游公司游客不足产生亏损。传统的旅游活动开展方式使得部分旅游公司拥有旅游资源过少，开展旅游活动成本过高，进而导致旅游公司收益减少。而我国目前旅游资源学的研究仍然以概念性为主，缺少定量的分析。随着旅游业的不断发展，旅游资源研究面临着与实际情况脱节的问题。这表明对旅游资源的研究必须在之前的理论和方法上有新的突破，实现旅游资源的定量分^[1]。在本文中，将某一时间某一旅游线路上开展旅游活动的游客资源称为旅游线路资源，旅游公司会根据某一时间某一条线路上自身拥有的旅游线路资源数目来规划旅游团，这个规划过程通常会受到天气、交通、住宿、成本等因素的限制。因此当旅游线路资源分布不均时，可能会出现旅游线路资源过多或旅游线路资源不足难以正常开展旅游活动的情况，影响旅游公司的发展，进而影响旅游业的发展。本文将旅游线路资源（即旅游线路上的游客资源）看作可交易的商品，使得分布在不同旅游公司的旅游线路资源可以被重新分配，进而使旅游线路资源分布均匀，促进旅游公司和旅游业的发展。然而在实际情况下由于各公司的信息不公开，任一家旅游公司都不可能掌握其他旅游公司旅游线路资源的信息，使得不同旅游公司的旅游线路资源很难进行交易。

随着互联网技术的快速发展，如今旅游信息的发布、游客参团等均可在互联网平台进行，互联网的出现为旅游线路资源的整合创造了新的可能。本文构建了一个旅游资源中间商（即互联网交易平台），假定所有游客都在在互联网平台进行报名，即将分散的旅游线路资源聚集在一起。在互联网的环境中，旅游公司要确定对旅游线路资源的价值评估，旅游公司根据自身需求以及对旅游线路资源的价值评估向旅游资源中间商（互联网交易平台）提交需求，旅游资源中间商根据各旅游公司的需求以及自身利益对旅游线路资源进行分配，从而解决了部分旅游公司因为旅游资源不足难以正常开展旅游活动的问题,最大化旅游资源中间商的收益。

本文将在互联网环境下将旅游资源分配问题转化为商品交易问题，并使用组合拍卖机制进行求解，即对组合拍卖中的胜者决定问题进行求解。通过分配算法将资源分配给旅游公司，解决旅游资源分布不均匀的问题，最大化中间商的收益，为实际旅游资源分配提供指导意见。

1.2 国内外研究现状

近些年来，经济学、计算机科学在各行业电子市场的市场机制设计上起到了重要的作用^[2]，旅游业是一个典型的网络业务，旅游业中最重要的一个问题是需求和供给的匹配，而拍卖是解决这一类问题的一个有效方法，即将拍卖理论用于旅游业来进行旅游资源分配^[3]。旅游线路资源的分配问题本质上是分散资源约束调度问题（Resource-Constrained Project Scheduling Problem, RCPSP），属于NP-hard问题，近年来一直受到重点关注和研究^[4]。旅游资源分配问题属于受限资源调度问题，许多学者使用拍卖理论来解决受限资源调度问题，Wen Song等^[5][6]设计了一个基于组合拍卖的方法来解决分布式资源受限多项目调度问题(DRCMPSP)，Rezvan Alipoor Sabzevari等^[7]使用双边组合拍卖模型解决云计算中的资源分配问题，Wang等^[8]基于拍卖的协商机制解决了住房建筑业中的资源调度，并评估其在负载均衡和资源利用方面的效率。S. J. Rassenti等^[9]基于组合拍卖机制解决了机场停机坪调度问题。在使用拍卖问题解决旅游资源分配的研究上，Marentakis等^[10]提出一种将旅游资源拍卖给消费者市场的概念架构，将旅游资源作为可以拍卖的商品，其中卖家提供可用的资源和服务,而移动的旅客根据位置获取旅游资源。这种思想为本文提供了指导，本文将旅游线路资源看成可在线交易的商品进行拍卖。

随着拍卖理论的关注度的不断增高，数以百计的拍卖网站和在线交易平台在B2B和B2C市场上涌动出来。一些学者开始使用拍卖理论解决实际市场中的拍卖问题。Avrim Blum等^[11]研究了买家和卖家在不同时间进入市场对市场上的一种商品进行买卖的在线市场清仓问题,并提出了一种近似最优激励兼容的算法来最大化社会福利。Peter R. Wurman等^[12]考虑了周期双边拍卖机制，并分析了在这多个买家和卖家的拍卖下参与者的经济激励，同时对拍卖人的任务进行了计算分析并提出了处理投标和计算分配的有效算法。Jonathan Bredin等^[13]提出并评估在双边拍卖市场中动态匹配智能体的一般框架，多位买家和卖家随时间推移对单一商品进行购买和出售。Faria Nassiri-Mofakham等^[14]分析了多属性双边拍卖中投标人的投标策略，这种策略可以被用于多属性双边拍卖中投标人的自动投标。

组合拍卖^[15]是拍卖的一种，但与传统的拍卖方式不同，组合拍卖允许竞价人对多种商品的组合进行竞价，组合拍卖在分配多商品时效率更高且能够有效地提高组合物品的价值。和传统拍卖相比，组合拍卖也带来了巨大的挑战，包括计算、经济等方面的挑战。其中的一个计算问题就是当投标被提交给拍卖商之后拍卖商如何有效地决定分配，即胜者决定问题。本文使用一种基于组合拍卖的方法对旅游资源分配问题进行求解，旅游公司对旅游资源中间商拥有的资源进行竞标，中间商根据旅游公司的投标进行资源分配。本文通过两种不同的旅游资源分配算法，将旅游资源中间商拥有的旅游资源分配给旅游公司，解决组合拍卖中的胜者决定问题，最大化旅游资源中间商的收益。针对交易市场何时开展匹配的研究中，有两种主流规则，一是集合拍卖，拍卖者人数和资源数量固定，在所有拍卖者确定自己的策略后进行匹配；二是连续拍卖，一旦有新的拍卖者或资源进入市场则立刻进行匹配^[16][17],本文采用集合拍卖规则，即参与拍卖的旅游公司数目和旅游资源数目固定。对于胜者决定问题的求解，最初采用的是精确算法^[18]，如：穷举法^[19]，动态规划法^[20]，分支定界法^[21]。但随着问题的规模越来越大，使用精确算法进行求解花费时间迅速增加，研究人员开始尝试使用近似算法对胜者决定问题进行求解。Wen Song等^[5][6]使用贪心算法和基于分支界定法的改进贪心算法来求解组合拍卖中的胜者决定问题，Rezvan Alipoor Sabzevari等^[8]则使用独立成分分析法（ICA）进行求解。Viswanath Avasarala等^[22]提出了种子遗传算法基于组合拍卖机制求解资源分配中的胜者决定问题。Robert，C.Holte^[23]使用并分析了爬山算法在求解组合拍卖胜者决定的性能。Masaya Mito^[24]等使用了三种启发式出价排序方案对组合拍卖中的胜者决定问题进行求解。Mu Xia等^[25]将双边组合拍卖转换为单边组合拍卖，再将单边组合拍卖问题转化为多维背包问题，即将求解双边组合拍卖的胜者决定问题转化为求解多维背包问题，背包问题是常见的最优化问题。可见胜者决定问题的本质为最优化问题，最优化问题通常可使用遗传算法^[26]、分支界定法^[25]等进行求解。另外Tuomas Sandholm等^[27]广泛研究了组合拍卖市场的设计，包括：拍卖、反向拍卖、交换、单一单位、多单位、自由处置、非自由处置，并对各种不同的组合拍卖市场中胜者决定问题的求解难易程度进行了分析。

1.3 主要工作和技术路线

本文针对旅游公司在旅游线路上游客资源的不足以及旅游资源交易困难的问题，构建了旅游资源中间商，使用基于组合拍卖的旅游资源分配算法，帮助旅游资源中间商分配旅游资源，以解决旅游公司旅游线路资源不足的问题同时使旅游资源中间商利益最大化。本文拟在互联网环境下，要求旅游公司提供旅游线路资源的参数设定，将旅游资源线路看作可交易的商品，从旅游资源中间商的角度出发，分析并研究两种不同的旅游资源分配算法进行资源分配的效率。

本文的主要研究内容有以下几个方面：

1. 构建基于组合拍卖旅游资源市场模型，包括旅游资源交易者模型和旅游资源中间商模型。对旅游资源分配问题进行描述并将其形式化为组合拍卖。
2. 根据旅游资源市场模型，设计贪心算法和微生物遗传算法对旅游资源分配问题进行求解，帮助旅游资源中间商进行资源分配，从而最大化中间商收益。
3. 根据旅游资源市场模型，确定旅游资源分配算法效率的评估标准，本文从分配率、单位支付金额、旅游资源中间商总成本，这三个方面对旅游资源分配算法进行了对比和分析。

本文技术路线如下图所示：

图1-1 技术路线图

1.4 论文结构

第1章介绍了本文的研究背景及意义，从部分旅游公司旅游线路资源不足出发介绍了本文的研究意义和需解决的问题，然后详细介绍了国内外相关研究现状，包括将拍卖应用到不同领域的方法以及求解组合拍卖问题的算法的研究现状，最后简单描述了本文的研究思路和方法。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：