基于约束的餐厅台位管理 毕业论文外文翻译译文.doc

第 6 页 共 6 页 基于约束的餐厅台位管理alfio vidotto，kenneth n. grown，j. christopher beck摘要 餐厅台位管理在餐厅盈利和客户体验两方面起着关键作用。本文所要解决的是一个复杂的动态的组合问题餐厅台位配置。我们将展示如何在既定条件下，将有限的餐厅台位扩展生成灵活多变的餐厅台位配置方案，使其能应付不同顾客的不同要求。本文描述了一个可实现向用户提供实时建议的系统，该系统目前正在一间餐厅中运行。关键词：约束；变化；不确定性；餐厅管理 1.引言 有效的餐厅台位管理在提高一间餐厅的盈利能力是至关重要的无效的台位管理意味着，该餐厅将要失去潜在的顾客，但过多订单却意味着顾客被搁置，他们会产生不满意和受欺骗的感觉，不想再光顾这间餐厅。此外，客户的行为是不确定的，台位配置计划相应地应该是灵活的，或者说是能迅速地不断改变的，以避免过多顾客被搁置。餐厅经理面临着一系列的问题：最后的四人桌应该提供给二人聚餐吗？我们应该预留一个常客的高级台位多长时间呢？在晚上8点后还可以提供一个四人聚餐的台位吗？如果在晚上7点时没有台位，新订单应该安排在哪个时间呢？当一个聚餐超过了预定的时间，我们可以重新分配聚餐顺序以避免顾客被搁置吗？当聚餐被取消后，我们可以再接上后续的聚餐来空出另一个台位？在计算机领域里，餐厅台位管理是一个动态的受约束的组合优化问题餐厅必须在现实中管理订单和处理突发事件下，最大限度地发挥台位的效率。 在本文中，我们描述了一个解决餐厅台位管理问题的实施方案，帮助管理者回答上述问题。该解决方案在满足既定的约束条件下，同时又提高了灵活性和稳定性。我们描述的这个系统目前在一家餐馆测试。在本文的其余部分安排如下：第2节介绍了餐厅台位管理问题的更多细节，并介绍了一间与本课题有关的餐厅。第3节分析满足限定条件的必要元素。第4节提出了一个基本的约束模型和搜索算法。第5节调整这模型以提高灵活性，以进一步搜索更灵活的计划。而第6节通过我们的方法来找到一个稳定的计划。第7节展示我们实现的系统的用户界面。最后，第8节描述了结论和今后的工作。2.餐厅台位管理 eco1是在道格拉斯科克城的一个有名的中等餐厅，每周都有非常高的客流量。它也是发生在2000年的第一个开创了利用计算机互联网来解决这问题的先例，即e-mail预订。餐厅设有23桌，从2到8（图1）大小不等。一些台位的容量依赖于其他台位的情况：例如，台位2和台位15都可以坐6个座位，但当其中一个台位是由5或6个人就餐时，那么另一桌就容纳最多不超过4个人。这些台位也可以是这样配置：例如，双人桌21和22可以拼在一起来容纳3-5个人用餐。利用合并的台位来举行聚会时，聚餐最多不能超过30人。这里有超过100种不同的可设计的台位安排，因此这餐厅的容量范围从85到94。在这餐厅的晚上聚会在下午4点开始，而最后的聚会只能举行到晚上10:30。在这些条件下，餐厅旨在每个晚上接待190和210个顾客现实却非如此，造成这结果的原因是台位没有被很好地被利用；更严重地是，厨房还被拉伸以便能及时提供食物。eco的台位管理，就像大多数的餐厅，要应付两个阶段的问题：预订和现场管理.图1.餐厅的布局 在预订阶段，老板要与顾客商讨聚餐开始时间以使顾客的要求得到满足，同时要安排能够实现既定营业额的台位安排方案。通常情况下，老板将预留台位来应对各种预订要求，而这几乎不会改变；当一个请求不能被容纳在预订表中时，顾客必须被说服接受其他时间，不然他们的请求将被拒绝。然而，利用就餐顺序的再分配也可以容纳这些新的请求，这也是可实现的。在某些情况下，为了保持一个既定的计划，餐厅将删除一个预定，或者建议另一个时间，哪怕仍有一个台位是可用的。此外，老板必须根据订单的特性（包括时间，星期几，和聚会的性质）估计预期的就餐时间。 在现场管理方面，情况就完全不同了。到了夜晚餐厅按照既定的预订表营业。客户已经被安排到既定的时间，此时餐厅的目标是使顾客能在尽量不受搁置的情况下就坐。当发生改变时楼层经理就得修改餐厅台位计划，以及接受或拒绝“不速之客”使临时到达餐厅的客户无须任何提前预订。楼层管理中的问题是每一个顾客的情况都是无法提前预知的他们可能会迟到，可能无法来就餐，可能需要较长时间也可能比预期的要短，可能会临时改变他们就餐的地方大小，当然他们可能认为他们已经提前订单，其实没人记录他的订单。此时楼层经理必须立即应付这些问题，在漫漫长夜里满足顾客所有的要求，使每一个顾客都满意归去。 我们预期的解决办法是建造一个互动的软件工具，协助餐厅人员完成预订和现场管理工作。我们的研究课题的目标是测试在既定条件下能否提供多个关于这个多变的和不确定的问题的解决方案。如果该研究是成功的，一个新的工具将被开发，并纳入客户关系管理软件。3.解决约束问题 一个约束问题（csp）是由已预订的聚会构成：x1，x2，.，xn，与之相应需要的台位：d1，d2，dn，和限定条件：c1,c2,cm所构成的。每个限定条件都是由聚会所需要的台位和餐厅所拥有的台位间的关系所构成的数组。一种关系就是这个解决方案的一些或全部的等值，xi= vi，xj= vj.。csp的解决方案就是一个完整的配置方案，即所有聚会都得到安排，x1= v1，x2= v2,.，xn= vn，即满足所有的条件。解决csp问题的标准方法是基于回溯搜索交错约束传播。关于这方面的约束编程的内容可在2，3调查的最近研究中找到。 在搜索中，已经经过测试过的台位安排必须被指定为检索算法的一部分，并且对搜索树的大小起着一定的作用。可变排序搜索方法选择当前最少台位或者是台位多少与满足条件的预订聚会的最小比。在csp的一个例子中，对应一个运行方式的单个搜索在独自运行中会受困在错误的搜索树的区域。为了避免这种情况，随机重新搜索已经被采纳4作为单个搜索，如果在既定的时间下没有找到运行方式，搜索将再次启动。突破局限和值排序的过程是随机完成的，所以每次重启探索一条不同的道路。类似地，算法组合5交织成一组随机化算法。该6搜索强度是通过合并多个变量和既定时间下重新启动的值排序启发式来提高的。 在限定进程中，未分配变量的台位将通过一个方法被删除，即删除这些不能出现在这个能改变现时的情况的解决方案中的变量。例如，如果我们有条件x(p1t3,p3t3)c4. (p3t3)|(p2t4)c5. 3+(p2=t2)4c6. p1.size+p2.size+p3.size=12c7. p3.size+p4.size+p5.size=12c8. p4p5fig.3. 对fig.2.问题的csp过程4.解决具体的问题（略）5.灵活性和优化（略）6.资源最优化（略）7.多方位台位管理建议（略）本文译自：alfio vid