基于約束的餐廳臺位管理外文翻譯譯文（節(jié)選）

1、<p><b>　　中文3060字</b></p><p>　　本文譯自：Alfio Vidotto, Kenneth N. Brown, J. Christopher Beck, Managing restaurant tables using constraints, Knowledge-Based Systems, Volume 20, Issue 2, March 2007

2、. </p><p>　　基于約束的餐廳臺位管理</p><p>　　Alfio Vidotto，Kenneth N. grown，J. Christopher Beck</p><p><b>　　摘要</b></p><p>　　餐廳臺位管理在餐廳盈利和客戶體驗兩方面起著關(guān)鍵作用。本文所要解決的是一個復(fù)雜的動態(tài)的組合

3、問題——餐廳臺位配置。我們將展示如何在既定條件下，將有限的餐廳臺位擴(kuò)展生成靈活多變的餐廳臺位配置方案，使其能應(yīng)付不同顧客的不同要求。本文描述了一個可實現(xiàn)向用戶提供實時建議的系統(tǒng)，該系統(tǒng)目前正在一間餐廳中運行。</p><p>　　關(guān)鍵詞：約束；變化；不確定性；餐廳管理 </p><p><b>　　1.引言</b></p><p>　　有效的餐

4、廳臺位管理在提高一間餐廳的盈利能力是至關(guān)重要的——無效的臺位管理意味著，該餐廳將要失去潛在的顧客，但過多訂單卻意味著顧客被擱置，他們會產(chǎn)生不滿意和受欺騙的感覺，不想再光顧這間餐廳。此外，客戶的行為是不確定的，臺位配置計劃相應(yīng)地應(yīng)該是靈活的，或者說是能迅速地不斷改變的，以避免過多顧客被擱置。餐廳經(jīng)理面臨著一系列的問題：最后的四人桌應(yīng)該提供給二人聚餐嗎？我們應(yīng)該預(yù)留一個?？偷母呒壟_位多長時間呢？在晚上8點后還可以提供一個四人聚餐的臺位嗎？如

5、果在晚上7點時沒有臺位，新訂單應(yīng)該安排在哪個時間呢？當(dāng)一個聚餐超過了預(yù)定的時間，我們可以重新分配聚餐順序以避免顧客被擱置嗎？當(dāng)聚餐被取消后，我們可以再接上后續(xù)的聚餐來空出另一個臺位？在計算機(jī)領(lǐng)域里，餐廳臺位管理是一個動態(tài)的受約束的組合優(yōu)化問題——餐廳必須在現(xiàn)實中管理訂單和處理突發(fā)事件下，最大限度地發(fā)揮臺位的效率。</p><p>　　在本文中，我們描述了一個解決餐廳臺位管理問題的實施方案，幫助管理者回答上述問題。

6、該解決方案在滿足既定的約束條件下，同時又提高了靈活性和穩(wěn)定性。我們描述的這個系統(tǒng)目前在一家餐館測試。在本文的其余部分安排如下：第2節(jié)介紹了餐廳臺位管理問題的更多細(xì)節(jié)，并介紹了一間與本課題有關(guān)的餐廳。第3節(jié)分析滿足限定條件的必要元素。第4節(jié)提出了一個基本的約束模型和搜索算法。第5節(jié)調(diào)整這模型以提高靈活性，以進(jìn)一步搜索更靈活的計劃。而第6節(jié)通過我們的方法來找到一個穩(wěn)定的計劃。第7節(jié)展示我們實現(xiàn)的系統(tǒng)的用戶界面。最后，第8節(jié)描述了結(jié)論和今后的

7、工作。</p><p><b>　　2.餐廳臺位管理</b></p><p>　　Eco[1]是在道格拉斯科克城的一個有名的中等餐廳，每周都有非常高的客流量。它也是發(fā)生在2000年的第一個開創(chuàng)了利用計算機(jī)互聯(lián)網(wǎng)來解決這問題的先例，即E-mail預(yù)訂。餐廳設(shè)有23桌，從2到8（圖1）大小不等。一些臺位的容量依賴于其他臺位的情況：例如，臺位2和臺位15都可以坐6個座位，但

8、當(dāng)其中一個臺位是由5或6個人就餐時，那么另一桌就容納最多不超過4個人。這些臺位也可以是這樣配置：例如，雙人桌21和22可以拼在一起來容納3-5個人用餐。利用合并的臺位來舉行聚會時，聚餐最多不能超過30人。這里有超過100種不同的可設(shè)計的臺位安排，因此這餐廳的容量范圍從85到94。在這餐廳的晚上聚會在下午4點開始，而最后的聚會只能舉行到晚上10:30。在這些條件下，餐廳旨在每個晚上接待190和210個顧客——現(xiàn)實卻非如此，造成這結(jié)果的原因

9、是臺位沒有被很好地被利用；更嚴(yán)重地是，廚房還被拉伸以便能及時提供食物。Eco的臺位管理，就像大多數(shù)的餐廳，要應(yīng)付兩個階段的問題：預(yù)訂和現(xiàn)場管理.</p><p><b>　　圖1.餐廳的布局</b></p><p>　　在預(yù)訂階段，老板要與顧客商討聚餐開始時間以使顧客的要求得到滿足，同時要安排能夠?qū)崿F(xiàn)既定營業(yè)額的臺位安排方案。通常情況下，老板將預(yù)留臺位來應(yīng)對各種預(yù)訂要

10、求，而這幾乎不會改變；當(dāng)一個請求不能被容納在預(yù)訂表中時，顧客必須被說服接受其他時間，不然他們的請求將被拒絕。然而，利用就餐順序的再分配也可以容納這些新的請求，這也是可實現(xiàn)的。在某些情況下，為了保持一個既定的計劃，餐廳將刪除一個預(yù)定，或者建議另一個時間，哪怕仍有一個臺位是可用的。此外，老板必須根據(jù)訂單的特性（包括時間，星期幾，和聚會的性質(zhì)）估計預(yù)期的就餐時間。</p><p>　　在現(xiàn)場管理方面，情況就完全不同了。

11、到了夜晚餐廳按照既定的預(yù)訂表營業(yè)?？蛻粢呀?jīng)被安排到既定的時間，此時餐廳的目標(biāo)是使顧客能在盡量不受擱置的情況下就坐。當(dāng)發(fā)生改變時樓層經(jīng)理就得修改餐廳臺位計劃，以及接受或拒絕“不速之客”——使臨時到達(dá)餐廳的客戶無須任何提前預(yù)訂。樓層管理中的問題是每一個顧客的情況都是無法提前預(yù)知的——他們可能會遲到，可能無法來就餐，可能需要較長時間也可能比預(yù)期的要短，可能會臨時改變他們就餐的地方大小，當(dāng)然他們可能認(rèn)為他們已經(jīng)提前訂單，其實沒人記錄他的訂單。此

12、時樓層經(jīng)理必須立即應(yīng)付這些問題，在漫漫長夜里滿足顧客所有的要求，使每一個顧客都滿意歸去。</p><p>　　我們預(yù)期的解決辦法是建造一個互動的軟件工具，協(xié)助餐廳人員完成預(yù)訂和現(xiàn)場管理工作。我們的研究課題的目標(biāo)是測試在既定條件下能否提供多個關(guān)于這個多變的和不確定的問題的解決方案。如果該研究是成功的，一個新的工具將被開發(fā)，并納入客戶關(guān)系管理軟件。</p><p><b>　　3.解

13、決約束問題 </b></p><p>　　一個約束問題（CSP）是由已預(yù)訂的聚會構(gòu)成：{X1，X2，...，Xn}，與之相應(yīng)需要的臺位：{D1，D2，…Dn}，和限定條件：{C1,C2,…,Cm}所構(gòu)成的。每個限定條件都是由聚會所需要的臺位和餐廳所擁有的臺位間的關(guān)系所構(gòu)成的數(shù)組。一種關(guān)系就是這個解決方案的一些或全部的等值，{Xi= vi，Xj= vj...}。CSP的解決方案就是一個完整的配置方案，即

14、所有聚會都得到安排，{X1= v1，X2= v2,,...，Xn= vn}，即滿足所有的條件。解決CSP問題的標(biāo)準(zhǔn)方法是基于回溯搜索交錯約束傳播。關(guān)于這方面的約束編程的內(nèi)容可在[2]，[3]調(diào)查的最近研究中找到。</p><p>　　在搜索中，已經(jīng)經(jīng)過測試過的臺位安排必須被指定為檢索算法的一部分，并且對搜索樹的大小起著一定的作用。可變排序搜索方法選擇當(dāng)前最少臺位或者是臺位多少與滿足條件的預(yù)訂聚會的最小比。在CSP

15、的一個例子中，對應(yīng)一個運行方式的單個搜索在獨自運行中會受困在錯誤的搜索樹的區(qū)域。為了避免這種情況，隨機(jī)重新搜索已經(jīng)被采納[4]——作為單個搜索，如果在既定的時間下沒有找到運行方式，搜索將再次啟動。突破局限和值排序的過程是隨機(jī)完成的，所以每次重啟探索一條不同的道路。類似地，算法組合[5]交織成一組隨機(jī)化算法。該[6]搜索強(qiáng)度是通過合并多個變量和既定時間下重新啟動的值排序啟發(fā)式來提高的。</p><p>　　在限定進(jìn)

16、程中，未分配變量的臺位將通過一個方法被刪除，即刪除這些不能出現(xiàn)在這個能改變現(xiàn)時的情況的解決方案中的變量。例如，如果我們有條件X<Y，且X和Y的域分別為{ 2，3，4，5}和{1，2，3，4}，這時，將4和5可以從X的域排除，以及將1和2從Y的域排除，因為這些值都不能滿足這個條件。減少域值相應(yīng)地也減少子樹中被探索的域大小。約束編程工具的成功很大一部分是由于高效域濾波算法進(jìn)行專門的限制;也就是[7]。</p><p

17、>　　動態(tài)問題就是解決正在執(zhí)行計劃時出現(xiàn)的問題——例如，在調(diào)度中，一臺機(jī)器可以熄火了，或計劃執(zhí)行中可能會由于供應(yīng)的遲到采取行動而造成延遲。動態(tài)CSP[8]模式根據(jù)不同問題而改變。這樣做的目的是為了以最小的成本去尋找新的解決方案，或使兩套解決方案之間的轉(zhuǎn)換成本最小。目前我們聚焦在這樣一個問題，即我們是否有多個解決這些變化的模式。[9]和[10]都是將來事件的變化的原因：[9]搜索能力和擴(kuò)展范圍有限在可執(zhí)行方案樹中起著約束作用; [1

18、0]測出POS的可選擇方案中，然后選擇其中具有最小遺憾值的方案。 [11]搜索具有最佳穩(wěn)定性的解決方案。他們與原來的解決方案作對比，并反復(fù)檢查是否需要重新分配一個變量或者兩個變量等，來解決新的問題。 [12]提出了特別的穩(wěn)定條件。某些方法為了避免不穩(wěn)定而提供穩(wěn)固的解決方案。在[13]排序問題中，其解決方法是通過加入靈活活動的持續(xù)時間來實現(xiàn)。更高級的方法[14]是在多變的情況下保證有既定的修復(fù)值供應(yīng)。</p><p&g

19、t;　　Fig.2.臨時面對的問題(左)；和一個應(yīng)對的方案（右）。</p><p>　　變量:{P1,P2,P3,P4,P5}</p><p>　　域:D1={T1,T2,T3,T4},D2={T2,T4},D3={T2,T3,T4},D4={T1,T2,T3,T4},D5={T1,T2,T3,T4}</p><p><b>　　限制條件：</b&g

20、t;</p><p>　　C1. all different([P1,P2,P3])</p><p>　　C2. all different([P3,P4,P5])</p><p>　　C3. (P2==T2)=>(P1≠T3,P3T3)</p><p>　　C4. (P3≠T3)||(P2≠T4)</p>

21、<p>　　C5. 3+(P2==T2)≦4</p><p>　　C6. P1.size+P2.size+P3.size<=12</p><p>　　C7. P3.size+P4.size+P5.size<=12</p><p>　　C8. P4<P5</p><p>　　Fig.3. 對Fig.

22、2.問題的CSP過程</p><p><b>　　4.解決具體的問題</b></p><p><b>　　（略）</b></p><p><b>　　5.靈活性和優(yōu)化</b></p><p><b>　?。裕?lt;/b></p><p&g