رویکردهای همسایگی جدید در الگوریتم ممتیک برای یافتن نوع مشتری

محورهای موضوعی : مهندسی کامپیوتر و فناوری اطلاعات

حامد شرافت مولا ¹ , هادی یعقوبیان ² , راضیه ملک حسینی ³ , کرم الله باقری فرد ⁴

1 - گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران
2 - گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران
3 - گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران
4 - گروه مهندسی کامپیوتر ، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

تاریخ دریافت : 1402/11/13 تاریخ پذیرش : 1402/12/21 تاریخ انتشار : 1403/05/10

کلید واژه: مدیریت درآمد, الگوریتم‌های فراابتکاری, الگوریتم ژنتیک, الگوریتم ممتیک,

چکیده مقاله :

سیستم‌های «مدیریت سود» امروزه به‌صورت فراوان در صنایع مختلفی استفاده می‌شوند. یکی از پایه‌های اصلی مدیریت سود، «برآورد تقاضا» است که بر اساس آن تقاضای محصولات و خدمات پیش‌بینی می‌شود. شناخت مشتریان و علایق آنها زیربنای برآورد تقاضاست و این شناخت با حل مسئله «کشف نوع مشتری» به‌دست می‌آید. به تازگی این مسئله با استفاده از روش فراابتکاری «ژنتیک» حل‌شده¬است و در این تحقیق با استفاده از رویکردهایی دیگر برای یافتن همسایگی، این مسئله را با روش فراابتکاری «ممتیک» حل خواهیم¬کرد. برای ارزیابی تحقیق خود، از داده‌های واقعی پنج هتل استفاده خواهیم¬کرد و در ادامه نشان می‌دهیم که روش پیشنهادی درمجموع با 10.5 درصد تعداد نسل کمتر نسبت به روش «ژنتیک» اولین راه‌حل قابل‌قبول مسئله را ارائه می‌دهد.

چکیده انگلیسی:

"Revenue management" systems are extensively utilized across various industries today. One of the primary pillars of revenue management lies in demand estimation, which predicts the demand for products and services. Understanding customers and their preferences forms the cornerstone of demand estimation, and this understanding is acquired through solving the "customer type discovery" problem. Recently, this problem has been addressed using the "genetic" meta-heuristic method. In this research, we propose solving this problem utilizing the "memetic" meta-heuristic method, employing alternative approaches to identify the neighborhood. By evaluating real data from five hotels, we demonstrate that our method offers the first viable solution to the problem, resulting in a total of 10.5% fewer iterations compared to the "genetic" method.

منابع و مأخذ:

[1] K. T. Talluri and G. J. Van Ryzin, The Theory and Practice of Revenue Management, vol. 68. Boston, MA: Springer US, 2004.
[2] P. Liu and S. Smith, “Estimating unconstrained hotel demand based on censored booking data,” Journal of Revenue and …, July 01, 2002. http://link.springer.com/10.1057/palgrave.rpm.5170015 (accessed February 21, 2018).
[3] A. Nikseresht and K. Ziarati, “Estimating True Demand in Airline’s Revenue Management Systems using Observed Sales,” Int. J. Adv. Comput. Sci. Appl., vol. 8, no. 7, pp. 361–369, 2017, doi: 10.14569/ijacsa.2017.080748.
[4] C. Y. Goh, C. Yan, and P. Jaillet, “Estimating Primary Demand in Bike-sharing Systems,” SSRN Electron. J., Jan. 2019, doi: 10.2139/ssrn.3311371.
[5] J. P. Newman, M. E. Ferguson, L. A. Garrow, and T. L. Jacobs, “Estimation of Choice-Based Models Using Sales Data from a Single Firm,” Manuf. Serv. Oper. Manag., vol. 16, no. 2, pp. 184–197, May 2014, doi: 10.1287/msom.2014.0475.
[6] A. Aouad, V. F. Farias, and R. Levi, “Assortment Optimization under Consider-then-Rank Choice Models,” SSRN Electron. J., Jun. 2015, doi: 10.2139/ssrn.2618823.
[7] A. Aouad, V. Farias, R. Levi, and D. Segev, “The approximability of assortment optimization under ranking preferences,” Oper. Res., vol. 66, no. 6, pp. 1661–1669, Nov. 2018, doi: 10.1287/opre.2018.1754.
[8] D. Bertsimas and V. V Mišic, “Data-driven assortment optimization,” Manage. Sci., vol. 1, pp. 1–35, 2015.
[9] S. Jagabathula, “Assortment Optimization Under General Choice,” Ssrn, pp. 1–51, 2014, doi: 10.2139/ssrn.2512831.
[10] S. Jagabathula and P. Rusmevichientong, “A Nonparametric Joint Assortment and Price Choice Model,” Ssrn, no. July, 2013, doi: 10.2139/ssrn.2286923.
[11] G. Gallego, H. Topaloglu, and others, Revenue management and pricing analytics, vol. 209. Springer, 2019.
[12] G. Bitran and R. Caldentey, “An overview of pricing models for revenue management,” Manuf. Serv. Oper. Manag., vol. 5, no. 3, pp. 203–229, 2003.
[13] S. Kunnumkal, “Randomization Approaches for Network Revenue Management with Customer Choice Behavior,” Prod. Oper. Manag., vol. 23, no. 9, pp. 1617–1633, Sep. 2014, doi: 10.1111/poms.12164.
[14] L. Chen and T. Homem-de-Mello, “Mathematical programming models for revenue management under customer choice,” Eur. J. Oper. Res., vol. 203, no. 2, pp. 294–305, Jun. 2010, doi: 10.1016/J.EJOR.2009.07.029.
[15] G. Vulcano, G. van Ryzin, and R. Ratliff, “Estimating Primary Demand for Substitutable Products from Sales Transaction Data,” Ssrn, no. August 2015, 2011, doi: 10.2139/ssrn.1923711.
[16] G. van Ryzin and G. Vulcano, “A Market Discovery Algorithm to Estimate a General Class of Nonparametric Choice Models,” Manage. Sci., vol. 61, no. 2, pp. 281–300, 2015, doi: 10.1287/mnsc.2014.2040.
[17] G. van Ryzin and G. Vulcano, “Technical Note—An Expectation-Maximization Method to Estimate a Rank-Based Choice Model of Demand,” Oper. Res., vol. 65, no. 2, pp. 396–407, 2017, doi: 10.1287/opre.2016.1559.
[18] S. Jagabathula, D. Mitrofanov, and G. Vulcano, “Inferring Consideration Sets from Sales Transaction Data,” SSRN Electron. J., 2019, doi: 10.2139/ssrn.3410019.
[19] M. HajMirzaei, K. Ziarati, and A. Nikseresht, “Discovering customer types using sales transactions and product availability data of 5 hotel datasets with genetic algorithm,” J. Revenue Pricing Manag., 2020, doi: 10.1057/s41272-020-00245-3.
[20] S. Jagabathula and G. Vulcano, “A Partial-order-based Model to Estimate Individual Preferences Using Panel Data,” SSRN Electron. J., no. April, 2017, doi: 10.2139/ssrn.2560994.
[21] H. Lee and Y. Eun, “Discovering heterogeneous consumer groups from sales transaction data,” Eur. J. Oper. Res., vol. 280, no. 1, pp. 338–350, Jan. 2020, doi: 10.1016/J.EJOR.2019.05.043.
[22] M. HajMirzaei, K. Ziarati, and A. Nikseresht, “A customer type discovery algorithm in hotel revenue management systems,” J. Revenue Pricing Manag., 2021, doi: 10.1057/s41272-020-00273-z.
[23] T. Bodea, M. Ferguson, and L. Garrow, “Data Set —Choice-Based Revenue Management: Data from a Major Hotel Chain ,” Manuf. Serv. Oper. Manag., vol. 11, no. 2, pp. 356–361, 2008, doi: 10.1287/msom.1080.0231.
[24] L. Davis, Handbook of genetic algorithms. 1996.
[25] D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization,” IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 67–82, 1997.
[26] J. C. Culberson, “On the futility of blind search: An algorithmic view of ‘no free lunch,’” Evol. Comput., vol. 6, no. 2, pp. 109–127, 1998.
[27] D. E. Goldberg and S. Voessner, “Optimizing global-local search hybrids.,” in GECCO, 1999, vol. 99, pp. 220–228.
[28] P. Moscato, “On evolution, search, optimization, GAs and martial arts: toward memetic algorithms. California Inst. Technol., Pasadena,” 1989.
[29] N. Krasnogor and J. Smith, “A tutorial for competent memetic algorithms: model, taxonomy, and design issues,” IEEE Trans. Evol. Comput., vol. 9, no. 5, pp. 474–488, 2005.
[30] Wang, C. (2022). Efficient customer segmentation in digital marketing using deep learning with swarm intelligence approach. Information Processing & Management, 59(6), 103085.
[31] Narayana, V. L., Sirisha, S., Divya, G., Pooja, N. L. S., & Nouf, S. A. (2022, March). Mall customer segmentation using machine learning. In 2022 International Conference on Electronics and Renewable Systems (ICEARS) (pp. 1280-1288). IEEE.
[32] Griva, A., Zampou, E., Stavrou, V., Papakiriakopoulos, D., & Doukidis, G. (2023). A two-stage business analytics approach to perform behavioural and geographic customer segmentation using e-commerce delivery data. Journal of Decision Systems, 1-29.

متن کامل:



New neighborhood approaches in memetic algorithm for customer …/ Sherafat-Moula, et al.

New neighborhood approaches in memetic algorithm for customer type discovery

Hamed Sherafat-Moula1, S.Hadi Yaghoubyan2*, Razieh Malekhosseini3, Karamollah Bagherifard4

1 Department of Computer Engineering, Yasuj Branch, Islamic Azad University, Yasuj, Iran

Young Researchers and Elite Club, Yasuj Branch, Islamic Azad University, Yasuj, Iran

[e-mail]

2 Department of Computer Engineering, Yasuj Branch, Islamic Azad University, Yasuj, Iran

Young Researchers and Elite Club, Yasuj Branch, Islamic Azad University, Yasuj, Iran

[e-mail]

3 Department of Computer Engineering, Yasuj Branch, Islamic Azad University, Yasuj, Iran

Young Researchers and Elite Club, Yasuj Branch, Islamic Azad University, Yasuj, Iran

[e-mail]

4 Department of Computer Engineering, Yasuj Branch, Islamic Azad University, Yasuj, Iran

Young Researchers and Elite Club, Yasuj Branch, Islamic Azad University, Yasuj, Iran

[e-mail]

 

Abstract: "Revenue management" systems are extensively utilized across various industries today. One of the primary pillars of revenue management lies in demand estimation, which predicts the demand for products and services. Understanding customers and their preferences forms the cornerstone of demand estimation, and this understanding is acquired through solving the "customer type discovery" problem. Recently, this problem has been addressed using the "genetic" meta-heuristic method. In this research, we propose solving this problem utilizing the "memetic" meta-heuristic method, employing alternative approaches to identify the neighborhood. By evaluating real data from five hotels, we demonstrate that our method offers the first viable solution to the problem, resulting in a total of 10.5% fewer iterations compared to the "genetic" method.

Keywords: revenue management, meta-heuristic algorithms, genetic algorithm, memetic algorithm

JCDSA, Vol. 2, No. 5, Spring 2024	Online ISSN: 2981-1295	Journal Homepage: https://sanad.iau.ir/en/Journal/jcdsa
Received: 2024-02-02	Accepted: 2024-05-08	Published: 2024-06-15
CITATION	Sherafat, M.H., et al., "New neighborhood approaches in memetic algorithm for customer type discovery", Journal of Circuits, Data and Systems Analysis (JCDSA), Vol. 2, No. 5, pp. 34-44, 2024. DOI: 00.00000/0000
COPYRIGHTS	©2024 by the authors. Published by the Islamic Azad University Shiraz Branch. This article is an open-access article distributed under the terms and conditions of the Creative Commons Attribution 4.0 International (CC BY 4.0) https://creativecommons.org/licenses/by/4.0

 

* Corresponding author

 

Extended Abstract

1-       Introduction

Earnings management systems are in use in many industries. Maximum profit or revenue can be achieved using revenue management systems and this is a result of the deregulation of the US airline industry in 1978 [1]. Profit management helps in making important business decisions that directly affect the purchasing behavior of customers and consequently the business revenue.

Finding customer demand is known as “demand estimation” and this prediction describes which customers will come and which products they will buy [2-5]. The product offering decision is known as "bundle optimization" which considers what products should be available to customers in a specific time period [6-9]. Pricing strategy is a term used to refer to the procedure that determines dynamic pricing policies and their relationship to revenue management [10-12]. "Demand estimation" is one of the most important stages of the profit management process. At this stage, we should have a clear view of customers and their list of product preferences.

The amount of demand for each product in a period of time can be found by obtaining two main data "products available for sale" and "types of customers"; Therefore, demand estimation may directly depend on finding exact types of customers. As mentioned, finding exact customer types among all factorial types is classified as NP-hard problems [16]. Note that "Sales Transactions" and "Product Availability" over a period of time are the only available data in this problem, and customer types must be inferred from this data. The name of this problem is "discovery of customer type".

2-       Methodology

The problem of "customer type discovery" is investigated with many mathematical approaches. Most of these researches use "choice-based demand estimation" models [16-18]. Recently, the idea of ​​using meta-heuristics to find customer types was presented by Haj Mirzaei et al [19]. They presented a genetic algorithm to find suitable customer types from 5 real hotel datasets and solved the problem of customer type discovery.

Finding an acceptable solution using this approach is time-consuming and may not be suitable for some business applications that require immediate results. The use of "local search" algorithm can provide faster solutions, and the connection of "local search" and "genetic" algorithm can help for "faster convergence". The present research is an attempt to find the first acceptable solution to the customer type discovery problem with the least possible generation in meta-heuristic algorithm. The main idea of ​​this will be through the use of "local search" with the genetic algorithm. In this research, different local search approaches will be presented, so that by using them in the local search of the memetic algorithm, we can obtain the first acceptable solution of the problem faster (by reducing the number of generations) compared to the genetic algorithm.

After entering the type of customer in a time period, the customer chooses the product with the highest rank from his list of preferences in that period. If the customer cannot buy a product, he chooses the zero product and leaves the market. The customer entry rate in each period is discrete and homogeneous with a probability of 0 < λ < 1, which is considered the same in all periods. The term "consistency" is used because no one can truly tell which type of customer entered a period. Therefore, we can only find out which type of customer is compatible.

Evolutionary Algorithms (EA) are suitable for cases like customer type discovery problem. As mentioned in the literature review section, genetic algorithm has recently been able to perform better than mathematical approaches for problem solving. Pure evolutionary algorithms are more efficient in searching the problem space when combined with other techniques, such as local searches [25]-[27]. Therefore, the use of neighborhood makes it possible to use local search together with the genetic algorithm [19]. The memetic algorithm is a combination of genetic and memetic evolution We will use them in this research [28].

3-       Results and discussion

For the evaluation, we will use the dataset of five Continental hotels located in the United States. This dataset mainly consists of travel information of people who have booked rooms for business purposes. This dataset is publicly available and used as a benchmark for the customer type discovery problem. The data span is from March 12, 2007 to April 15, 2007, which includes 34 days [23]. Reservations are made through various channels such as travel agencies, hotel operators, personal visits and hotel websites. To evaluate the efficiency of our local search approaches, we implemented the mentioned three approaches with the memetic algorithm and compared it with the genetic method [19].

For both approaches (memetic and genetic), we have created an initial random population with a number of 25. The test is to show the speed of convergence in the initial phase (convergence of the population from unacceptable solutions to acceptable solutions). In this test, when the first acceptable solution is created, we have prevented the algorithm from continuing. Each experiment was repeated 30 times and the average results were reported. The results can be seen in Table (2).

4-       Conclusion

If we consider each customer type as a preferred list of products, discovering customer types is the first step in estimating product demand and one of the first steps in pricing strategy. If sales transactions and product availability data are used, finding customer types with meta-heuristic methods is challenging due to lack of data. In some applications, finding the first acceptable solution in a short time is more challenging than finding the optimal solution.

 

 

رویکردهای همسایگی جدید در الگوریتم ممتیک

برای یافتن نوع مشتری

حامد شرافت‌مولا1، هادی یعقوبیان2*، راضیه ملک‌حسینی۳، کرم‌الله باقری‌فرد ۴

1- گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

باشگاه پژوهشگران جوان و نخبگان، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

[e-mail]

2- گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

باشگاه پژوهشگران جوان و نخبگان، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

[e-mail]

۳- گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

باشگاه پژوهشگران جوان و نخبگان، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

[e-mail]

۴- گروه مهندسی کامپیوتر، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

باشگاه پژوهشگران جوان و نخبگان، واحد یاسوج، دانشگاه آزاد اسلامی، یاسوج، ایران

[e-mail]

چکیده: سیستم‌های «مدیریت سود» امروزه به‌صورت فراوان در صنایع مختلفی استفاده می‌شوند. یکی از پایه‌های اصلی مدیریت سود، «برآورد تقاضا» است که بر اساس آن تقاضای محصولات و خدمات پیش‌بینی می‌شود. شناخت مشتریان و علایق آنها زیربنای برآورد تقاضاست و این شناخت با حل مسئله «کشف نوع مشتری» به‌دست می‌آید. به تازگی این مسئله با استفاده از روش فراابتکاری «ژنتیک» حل‌شده­است و در این تحقیق با استفاده از رویکردهایی دیگر برای یافتن همسایگی، این مسئله را با روش فراابتکاری «ممتیک» حل خواهیم­کرد. برای ارزیابی تحقیق خود، از داده‌های واقعی پنج هتل استفاده خواهیم­کرد و در ادامه نشان می‌دهیم که روش پیشنهادی درمجموع با 10.5 درصد تعداد نسل کمتر نسبت به روش «ژنتیک» اولین راه‌حل قابل‌قبول مسئله را ارائه می‌دهد.

واژه‌های کلیدی: مدیریت درآمد، الگوریتم‌های فراابتکاری، الگوریتم ژنتیک، الگوریتم ممتیک

DOI: 00.00000/0000		نوع مقاله: پژوهشی
تاریخ چاپ مقاله:  26/03/1403	تاریخ پذیرش مقاله:  19/02/1403	تاریخ ارسال مقاله: 13/11/1402

 

 

1-        مقدمه

سیستم‌های «مدیریت سود¹» در صنایع زیادی در حال استفاده است. حداکثر سود یا درآمد را می‌توان با استفاده از سیستم‌های مدیریت درآمد به‌دست آورد و این امر حاصل مقررات‌زدایی صنعت هواپیمایی ایالات‌متحده در سال 1978 است [1]. مدیریت سود به تصمیم‌گیری‌های مهمی در کسب‌وکار کمک می‌کند که مستقیماً بر رفتار خرید مشتریان تأثیر می‌گذارد و درنتیجه، بر درآمد کسب‌وکار تأثیر می‌گذارد. این تصمیمات را می‌توان در سه بخش، دسته‌بندی کرد:

1.       تقاضای مشتریان برای محصولات؛

2.       محصولاتی که ارائه می‌شوند؛

3.       قیمت‌هایی که باید ارائه شوند.

یافتن تقاضای مشتریان به‌عنوان «برآورد تقاضا²» شناخته می‌شود و این پیش‌بینی توصیف می‌کند که ‌چه مشتریانی خواهند آمد و کدام محصولات را خریداری خواهند کرد [2-5]. تصمیم «ارائه محصولات» به‌عنوان «بهینه‌سازی مجموعه‌ای³» شناخته می‌شود که در نظر می‌گیرد چه محصولاتی باید در یک دورۀ زمانی خاص در دسترس مشتریان باشد [6-9]. استراتژی قیمت‌گذاری، اصطلاحی است که برای اشاره به رویه‌ای استفاده می‌شود که سیاست‌های قیمت‌گذاری پویا و ارتباط آن‌ها با مدیریت درآمد را تعیین می‌کند [10-12]. «برآورد تقاضا» یکی از مهم­ترین مراحل فرایند مدیریت سود است. در این مرحله باید دید روشنی از مشتریان و لیست ترجیحات آن­ها از محصولات داشته باشیم. در بازاری با n نوع محصول، هر «نوع مشتری⁴» با فهرستی مرتب از محصولاتی که ترجیح می‌دهد خریداری کند، نشان داده می‌شود [8، 13-15]. قابل‌ذکر است که هر مشتری می‌تواند کالایی را که در دسترس نیست (به‌دلیل عدم موجودی یا تغییر استراتژی فروش کسب) با کالایی که در دسترس است، جایگزین کند. چالش اصلی در این زمینه، تعداد بالقوۀ انواع مشتری است که با توجه به تعداد محصولات و در نظر گرفتن تعداد جایگزین برای محصولات به‌صورت فاکتوریل خواهد بود [16-17]. فرض کنید {1,2,3} محصول در کسب‌وکار وجود دارد و سه نوع مشتری C1={1,2}، C2={1} و C3={2,3} در یک بازۀ زمانی وارد بازار می‌شوند. مشتری نوع C1 در ابتدا ترجیح می‌دهد که محصول 1 را بخرد؛ اما اگر ۱ در دسترس نباشد، به‌جای آن محصول 2 را خریداری می‌کند. نکته مهم این است که اگر هر دو محصول 1 و 2 در دسترس نباشد، او هیچ محصولی را خریداری نخواهد کرد و بازار را ترک خواهد کرد. «عدم خرید» با خرید محصول صفر (0) نمایش داده می‌شود. اگر همه محصولات مدنظر نوع مشتری در دسترس نباشند، او ترجیح می‌دهد محصول صفر را خریداری کند. بنابراین، محصول صفر به انتهای هر نوع مشتری اضافه خواهد شد. روش صحیح نمایش انواع مشتریان به این صورت خواهد بود: C1={1,2,0} C2={1,0} C3={2,3,0} .

میزان تقاضا برای هر محصول در یک دوره زمانی را می‌توان با به‌دست‌آوردن دو دادۀ اصلی «محصولات موجود برای فروش» و «انواع مشتری» پیدا کرد؛ بنابراین، برآورد تقاضا به‌طور مستقیم ممکن است به یافتن انواع دقیق مشتری بستگی داشته باشد. همان‌طور که گفته شد، یافتن انواع مشتریان دقیق در میان همۀ انواع که به‌صورت فاکتوریل است، در دسته مسائل NP-hard دسته‌بندی می‌شود [16]. قابل توجه است که «تراکنش‌های فروش» و در «دسترس بودن محصول» در یک دوره زمانی، تنها داده‌های قابل دسترس در این مسئله هستند و انواع مشتریان باید از این داده‌ها استنتاج شوند. نام این مسئله «کشف نوع مشتری⁵» است. مسئلۀ کشف نوع مشتری با رویکردهای ریاضی بسیاری مورد بررسی قرار می‌گیرد. اکثر این پژوهش‌ها از مدل‌های «برآورد تقاضا مبتنی بر انتخاب⁶» استفاده می‌کنند [16-18]. اخیراً ایده استفاده از روش فراابتکاری⁷ برای یافتن انواع مشتری توسط حاج‌میرزایی و همکاران ارائه‌شده است [19]. آنها یک الگوریتم ژنتیک برای یافتن انواع مشتری مناسب از 5 مجموعه دادۀ هتل واقعی ارائه دادند و مسئلۀ کشف نوع مشتری را حل کردند.

       یافتن راه‌حل قابل قبول با استفاده از این رویکرد، زمان‌بر است و ممکن است برای برخی از برنامه‌های کاربردی تجاری که احتیاج فوری به نتیجه دارند، مناسب نباشد. استفاده از الگوریتم «جستجوی محلی⁸» می‌تواند راه‌حل های سریعتری ارائه دهد و اتصال الگوریتم «جستجوی محلی» و «ژنتیک» می‌تواند برای «همگرایی سریعتر» کمک کند.    تحقیق حاضر تلاشی برای یافتن اولین راه‌حل قابل قبول مسئله کشف نوع مشتری با کمترین نسل ممکن در الگوریتم فرا ابتکاری است. ایده اصلی این امر، به‌کارگیری «جستجوی محلی» با الگوریتم ژنتیک خواهد بود. در این تحقیق رویکردهای مختلف جستجوی محلی ارائه خواهد شد تا با استفاده از آن‌ها در جستجوی محلی الگوریتم ممتیک، بتوانیم اولین راه‌حل قابل قبول مسئله را سریع­تر (از طریق کم‌کردن تعداد نسل‌های لازم) نسبت به الگوریتم ژنتیک به‌دست آورده شود.

       در ادامه این تحقیق به پیشینه تحقیق پرداخته می‌شود. سپس مسئله «کشف نوع مشتری» مورد بررسی قرارخواهد گرفت و بعد از آن به نحوه حل مسئله با کمک الگوریتم ممتیک و بررسی رویکردهای جدید همسایگی اشاره می‌شود و در بخش بعدی، رویکردهای مدنظر مورد مقایسه قرار می‌گیرند و بخش نتیجه­گیری پایان این تحقیق خواهد بود.

1-       ادبیات و پیشینه تحقیق

ون رایزین و ولکانو [16] مدل برآورد تقاضای غیرپارامتریک کلی را برای پیداکردن انواع مشتری از تراکنش‌های فروش و داده‌های در دسترس بودن محصول، پیشنهاد کردند که شامل سه مرحلۀ اصلی است. مرحله اول این مدل از یک لیست محصول تکی برابر با تعداد محصولات برای حل اولیۀ رویکرد استفاده می‌کند. هر محصول تکی نشان دهنده یک نوع مشتری است که فقط یک محصول و صفر را شامل می‌شود. در مرحله دوم، نویسندگان از مدل تخمین تقاضا استفاده می‌کنند که بر اساس مدل تخمین، حداکثر احتمال برای ارزیابی برازندگی⁹ هر راه‌حل محاسبه می‌شود. در مرحله سوم، برنامۀ عدد صحیح مختلط¹⁰ (MIP) برای یافتن یک نوع مشتری جدید استفاده می‌شود که با اضافه کردن به آن، بهبود برازندگی راه‌حل فعلی را تضمین می‌کند. مراحل 2 و ۳ تکرار می‌شوند تا زمانی که رویکرد نتواند انواع مشتریان جدیدی را که برازندگی راه‌حل را بهبود می‌بخشد شناسایی کند. همچنین آنها در سال 2017 سعی کردند با استفاده از حداکثرسازی انتظار¹¹ (EM) و حل مسئله به صورت حداکثر احتمال، کارایی زمانی کار قبلی خود را بهبود بخشند [۱۷] و رویکرد آنها به عنوان حل مسئله کشف نوع مشتری درنظر گرفته شد. حاج‌میرزایی و همکاران [19] از الگوریتم ژنتیک برای پیداکردن انواع مشتری از 5 مجموعه دادۀ هتل استفاده کردند. نویسندگان از دو تابع برازندگی برای ارزیابی جمعیت استفاده کردند. تابع برازندگی اصلی، تابع حداکثر احتمال است که مشابه MLE است که در [16] برای راه‌حل‌های قابل قبول استفاده می‌شود. برای راه‌حل‌های غیرقابل‌قبول، نویسندگان از یک تابع برازندگی دیگری استفاده کردند. نویسندگان همچنین سعی کردند عملگرهای نمایش و بازتولید بهینه را برای کاربرد خود پیشنهاد کنند و توانستند دقت بهتری نسبت به روش ون رایزن داشته باشند.

در [20]، مدل تخمین تقاضای مبتنی بر انتخاب برای پیداکردن انواع مشتری در سه مرحله استفاده می‌شود: 1) ساخت نمودار غیر چرخه‌ای جهت‌دار برای هر نوع مشتری، 2) خوشه‌بندی آن، و 3) تخمین توزیع‌ها روی فهرست ترجیحی هر نوع مشتری. داده­های مورد استفاده برای این منظور از نوع تابلویی¹² هستند. در برخی بازارها، مانند بازارهای آنلاین و آن‌هایی که از برخی برنامه‌ها برای ثبت رفتار خرید مشتریان استفاده می‌کنند (برای مثال باشگاه وفاداری)، داده‌های موجود علاوه بر دقت، بسیار بیشتر از معاملات فروش و داده‌های موجود بودن محصول هستند. این نوع داده‌ها به داده‌های تابلویی معروف­اند و برای مجموعه‌هایی با داده­های کم، این رویکرد قابل استفاده نیست.

مدل «در نظر بگیرید؛ سپس انتخاب کنید» برای کشف انواع مشتری توسط جاگاباتولا و همکاران استفاده شد [18]. برای هر نوع مشتری، یک مجموعۀ «درنظرگرفتن توسط مشتری» برای استفاده از روش یادگیری ماشینی مبتنی بر داده استفاده شد و برای کشف هر مجموعۀ «درنظرگرفتن» از داده‌های خرده‌فروشی اشتراکی خودرو و داده‌های در دسترس بودن محصول استفاده شد و رویکردشان برای مواردی که احتیاج به دست­بندی مشتریان بر اساس مکان‌های جغرافیایی است مناسب خواهد­بود. لی و یون [21] رویکردی مبتنی بر مدل انتخاب برای یافتن انواع مشتریان ناهمگن با استفاده از داده‌های فروش و در دسترس بودن محصول پیشنهاد کردند. این رویکرد با اندازۀ ۱ آغاز می‌شود و سپس سعی می‌کند انواع مشتریان جدید را به این راه‌حل اضافه کند تا راه‌حل بهینه را بیابد. اندازه راه‌حل بهینه، تعداد انواع مشتری را با توجه به مجموعۀ دادۀ استفاده‌شده تعیین می‌کند و از بیشینه‌سازی انتظارات¹³ برای تخمین پارامترهای مدل انتخابی استفاده می­شود. حاج‌میرزایی و همکاران [22] رویکردی برای کشف نوع مشتری را بر اساس مسئلۀ سفارش خطی کلاسیک پیشنهاد کردند که از سه بخش تشکیل‌شده است. بخش 1 یک راه‌حل اولیه ایجاد می‌کند. بخش 2 احتمال هر نوع مشتری (PMF) را تخمین می‌زند. درنهایت، بخش ۳ مشتری جدیدی پیدا می‌کند. بخش‌های 2 و 3 تا رسیدن به معیارهای توقف تکرار می شوند.

در [30] به وظیفه چالش برانگیز افزایش رشد بازاریابی دیجیتال از طریق توسعه یک رویکرد تقسیم‌بندی مشتری کارآمد مبتنی بر هوش مصنوعی می‌پردازد. این مطالعه با استفاده از یک مدل یادگیری عمیق بدون نظارت برای شناسایی ویژگی‌های رفتاری کلیدی در داده‌های مشتری استفاده می‌کند ولی روش آنها نوع­ مشتری‌ها را پیدا نمی‌کند. در این تحقیق از مجموعه داده کگل استفاده شده و هر فاکتور شامل چندین خرید می­­شود و روش آنها برای محصولاتی که فاسدپذیری دارند قابل استفاده نیست. همچنین در [31]، با در نظر گرفتن اطلاعات نمونه، از تکنیک­های خوشه­بندی مانند K-means برای شناسایی بخش­های مشتری متمایز استفاده کردند. این تکنیک‌ها اجازه می‌دهد که با گروه‌بندی مشتریان بر اساس ویژگی‌های مشترک، از جمله جنسیت، سن، علایق و عادت‌های خرج کردن، بر پایه‌های کاربران بالقوه تمرکز کرد. آنها از پروفایل کاربر برای کار خود به استفاده کردند و کار آنها کارایی لازم را برای مجموعه داده­هایی که داده­های کمی دارند قابلیت استفاده ندارد. در [32] بر نقش حیاتی تقسیم‌بندی مشتری در هدایت شخصی‌سازی، تبلیغات هدفمند و استراتژی‌های تبلیغاتی تأکید می‌کنند و روند‌های ارزشمندی را هم به محققان ارائه می‌کنند. ادبیات موضوعی موجود در تحقیق آنها عمدتاً بر انواع تقسیم‌بندی منحصربه‌فرد، به‌ویژه تقسیم‌بندی رفتاری مبتنی بر پروفایل کاربر تکیه دارد که دید جامع نسبت به مشتری که متکی بر داده‌های خرید باشد را محدود می‌کند.

2-       شرح مسئله

این بخش، مسئلۀ «کشف نوع مشتری» را توضیح می‌دهد. جهت راحتی خواننده از نماد و اصطلاحات [19] استفاده می‌گردد. فرض کنید  محصولات خریداری‌شده در بازه‌¹⁴های زمانی  توسط انواع مشتریان ناشناخته که در تلاش برای یافتن آن‌ها هستیم، هستند. انتخاب محصول صفر توسط مشتری به معنای خریدن نکردن و خروج از بازار است. همانطور که قبلاً اشاره شد، هر نوع مشتری با لیست ترجیحی از محصولاتی که در آن محصول h بالاتر از j  قرار دارد، نشان داده می­شود C(h) < C(j)؛ یعنی مشتری خرید محصول h را به j ترجیح می‌دهد. لیست محصولات ارائه‌شده در هر دورۀ زمانی با St ⊆ N, 0 ∈ St ، که در آن St≥2 است (محصول صفر و حداقل یک محصول دیگر) مشخص می شود. پس از ورود نوع مشتری در یک بازۀ زمانی، مشتری محصولی را با بالاترین رتبه از لیست ترجیحات خود در آن دوره انتخاب می‌کند. اگر مشتری نتواند محصولی را بخرد، محصول صفر را انتخاب کرده و بازار را ترک می‌کند. نرخ ورود مشتریان در هر دوره گسسته و همگن با احتمال  است که در تمامی دوره‌ها یکسان در نظر گرفته می‌شود.

جدول (۱) نمونه‌ای از تراکنش‌های فروش و داده‌های در دسترس بودن محصول را پس از پیش‌پردازش مجموعۀ داده نشان می‌دهد. در این جدول 5 دوره زمانی و 5 محصول وجود دارد. در دوره 1، سه محصول برای فروش در دسترس (موجود) است و محصول 1 توسط مشتری خریداری‌شده است. در دوره 2 محصولات 1 و 2 و 5 موجود است و محصول 5 خریداری می‌شود. فرض کنید سه نوع مشتری وارد بازار می‌شوند: ،   و  . در دوره 1، مشتری  در این دوره سازگار¹⁵ است، یعنی اگر  وارد این دوره شود، محصول 1 خریداری می شود. اصطلاح «سازگاری» به این دلیل به کار می‌رود که هیچ‌کس نمی‌تواند به‌طور واقعی تشخیص دهد کدام نوع مشتری در یک دوره واردشده است. بنابراین، فقط می‌توانیم بفهمیم کدام نوع مشتری سازگار است. در دوره 2،  تنها نوع مشتری سازگار است. به این مورد دقت شود که در دوره 2،  سازگار نیست؛ زیرا اگر  در این دوره می‌رسید، مشتری محصول 1 را خریداری می­کرد. در دوره 4، هیچ نوع مشتری وارد نشده است. در دوره 5، هیچ محصولی خریداری نشده چرا که فقط نوع 2 و 3 مشتری سازگار باشد زیرا اگر  به این دوره برسد، محصول 3 را خریداری می‌کند. یافتن سازگاری انواع مشتری برای هر دوره، اولین گام فرایند در رویکردهای کشف بازار است. انواع مشتریان سازگار در دورۀ t با  نشان داده می‌شوند. برای مجموعه کامل انواع مشتری  و  که در آن  محصولات ارائه شده و  تراکنش دوره t است، انواع مشتری سازگار به صورت زیر پیدا می شود:

2-‏1-‏       مدل مبتنی بر انتخاب¹⁶

مدل انتخاب گسسته کلی در [15] پیشنهادشده است که از آن به‌عنوان یک مدل غیرپارامتریک برای یافتن احتمال خرید محصول  در بازه زمانی t استفاده می‌گردد:

(1)

که در آن منظور از عدم خرید، خرید محصول صفر یا عدم ورود مشتری است. برآوردگر حداکثر درستنمایی¹⁷ (MLE) برای برآورد تقاضا به شرح زیر استفاده می‌شود:

(2)

جدول (۱): در دسترس بودن محصول و نمونه تراکنش فروش

(3)

" P ، "NP"، "NA" به ترتیب مخفف Purchase، No-Purchase و No-Arrival است.

همان‌طور که قبلا ذکر شد، بازه T کل شامل سه نوع مختلف است:

			دوره
محصولات	1	2	3	4	5
1	بله	بله	خیر	خیر	خیر
2	بله	بله	خیر	خیر	خیر
3	بله	خیر	خیر	خیر	بله
4	خیر	خیر	بله	خیر	خیر
5	خیر	بله	بله	بله	خیر
تراکنش	1	5	4	NA	0
سازگاری	{1}	{2}	{1,2 }	-	{2,3}
نوع تراکنش

و حداکثر تخمین log-likelihood به شرح زیر است:

(4)

هنگامی  ارائه می‌شود، احتمال انتخاب یک محصول  توسط مشتریان در دوره t به صورت  است. بدیهی است که در صورت عدم ارائه  احتمال صفر خواهد بود. با جایگزین کردن تابع احتمال در معادله (5)، می‌توانیم داشته باشیم:

(5)

و پس از خلاصه‌سازی (6):

(6)

(7)

+ در (7)، عبارت اول نشان‌دهنده log-likelihood خرید کالا در دوره‌های خرید، عبارت دوم برای دوره‌های بدون خرید و عبارت آخر برای دوره‌های بدون ورود است. این تابع log-likelihood مشابه [16] است. معادله در x و λ قابل‌تفکیک است و به‌صورت سراسری در (x,λ) مقعر است. بنابراین، به‌راحتی می‌توانیم  را پیدا کنیم.      3-       ممتیک و حل مسئله «کشف نوع مشتری» الگوریتم‌های تکاملی18 (EA) برای موارد مشابه مسئله کشف نوع مشتری مناسب هستند. همان‌طور که در بخش بررسی ادبیات ذکر شد، اخیراً الگوریتم ژنتیک توانسته از رویکردهای ریاضی برای حل مسئله بهتر عمل کند. الگوریتم‌های تکاملی خالص در جستجوی فضای مسئله زمانی که با تکنیک‌های دیگر، مانند جستجوهای محلی ترکیب شوند، کارآمدتر هستند [25-27]. بنابراین، استفاده از همسایگی این امکان را می‌دهد از جستجوی محلی همراه با الگوریتم ژنتیک [19] استفاده شود. الگوریتم ممتیک، ترکیبی از تکاملی‌های ژنتیک و ممتیک است و در این تحقیق از آنها استفاده خواهیم کرد [28]. شکل (۱) روند کلی ممتیک را نمایش می‌دهد. در این بخش ساختار ممتیک مورد استفاده برای حل مسئله «کشف نوع مشتری» را شرح خواهیم داد. قابل توجه است که هدف اصلی این مقاله، نشان‌دادن تأثیر رویکردهایی است که برای جستجوی محلی در حل این مسئله استفاده‌شده است. برای درک این فرآیند، باید بین راه‌حل قابل‌قبول و غیرقابل‌قبول تمایز قائل شویم. فرض کنید راه‌حلی وجود دارد که شامل برخی از انواع مشتری است. برای ارزیابی این راه‌حل، ابتدا باید سازگاری هر دوره را با استفاده از  پیدا کنیم. پس از آن، اگر راه‌حلی همه دوره­ها را پوشش دهد و در همه دوره‌ها سازگار باشد، راه‌حلی قابل‌قبول است. ازنقطه‌نظر امکان‌سنجی، می‌توان فرآیند الگوریتم ممتیک (یا سایر تکاملی‌ها) را برای حل مسئله کشف نوع مشتری به دو فاز مختلف طبقه‌بندی کرد. فاز اول، از راه‌حل‌های غیرقابل‌قبول به راه‌حل‌های قابل‌قبول همگرا می‌شود و فاز دوم یافتن راه‌حل بهینه با استفاده از راه‌حل‌های قابل‌ قبول است. در تحقیق فعلی، اولین هدف تسریع فرآیند فاز اول باکمک جستجوی محلی است. هدف دوم در حیطه‌ی این تحقیق نمی‌گنجد. شبه کد الگوریتم ممتیک استفاده‌شده به شرح زیر است:          شکل (1): الگوریتم ممتیک [28]   1 Generate random initial population 2 Local search 3 Fitness evaluation 4 Repeat until (termination condition) 5 Single-point crossover Reproduction operators 6 Local search 7 Fitness evaluation 8 Survival selection 9 End repeat 3-‏1-‏       نحوه نمایش یک راه‌حل، شامل لیستی از انواع مشتری با اندازه حداقل یک است. هر نوع مشتری یک لیست ترجیحی از محصولات است که به محصول صفر ختم می‌شود. به‌عنوان‌مثال، راه‌حل زیر شامل سه نوع مشتری با اندازه‌های مختلف است.   3-‏2-‏       جمعیت اولیه در ابتدای کار الگوریتم، جمعیت اولیه تصادفی با اندازه ثابت تولید شده است. هر راه‌حل از جمعیت اولیه شامل تعدادی تصادفی از انواع مشتری و هر نوع مشتری شامل تعداد تصادفی از محصولات است.      محصولات تکراری در نوع مشتری و محصول صفر در ابتدای نوع مشتری مجاز نیستند. 3-‏3-‏       تابع برازندگی قبل از استفاده از تابع برازندگی برای ارزیابی یک راه‌حل، باید سازگاری آن راه‌حل را در تمام دوره‌ها پیدا کنیم. اگر حداقل یک دوره ناسازگار وجود داشته باشد، به معنای غیرقابل‌قبول بودن راه‌حل است و اگر دوره‌های ناسازگار وجود نداشته باشد، به معنای قابل‌قبول بودن راه‌حل است. تابع برازندگی زیر از دو بخش مجزا تشکیل‌شده است. قسمت اول  برای راه‌حل های غیرقابل قبول و قسمت دوم برای راه‌حل‌های قابل‌قبول استفاده می‌شود. بدیهی است که تابع برازندگی را پس از ارزیابی سازگاری دوره ها برای یک راه‌حل انتخاب می کنیم. کل دوره‌ها  می‌باشد که در آن   و  به ترتیب تعداد دوره های سازگار و ناسازگار را نشان می دهد. قابل توجه است که T شامل دوره‌های بدون ورود نمی‌شود. پارامتر  ثابت تنبیه است. در بخش دوم تابع برازندگی،  تابع (3) است که در بخش قبل توضیح داده شد. 3-‏4-‏       عملگر ترکیب تک نقطه ای برای اعمال عملگر ترکیب تک نقطه‌ای19 روی دو راه‌حل، نیمی از طول راه‌حل را به‌عنوان نقطه انتخاب کردیم. با استفاده از این کراس­اُوور، دو فرزند به وجود می­آید. 3-‏5-‏       عملگرهای تولید مثل انتخاب چرخ رولت برای انتخاب یکی از اپراتورهای تولید مثل زیر و اعمال آن برای فرزندان اعمال می شود: 1.       اضافه کردن یک نوع مشتری تصادفی با طول تصادفی به یک راه‌حل. 2.       حذف یک نوع مشتری تصادفی از یک راه‌حل. 3.       حذف یک محصول تصادفی از نوع مشتری تصادفی در یک راه‌حل. 4.       جایگزینی یک محصول تصادفی با محصول دیگری از نوع مشتری تصادفی در یک راه‌حل. 5.       اعمال یک کراس­اوور تک نقطه‌ای برروی دو نوع تصادفی مشتری از یک راه‌حل. 3-‏6-‏       انتخاب بازماندگان جمعیت زنده مانده شامل 80 درصد بهترین و 20 درصد از بدترین راه‌حل‌ها از جمعیت والدین و فرزندان است. در این تحقیق، جمعیت باقی­مانده را قبل از استفاده در تکرار بعدی به هم می‌ریزیم. 3-‏7-‏       جستجوی محلی ادعا می‌شود که موفقیت ممتیک به‌دلیل مبادله بین قابلیت‌های اکتشاف و توانایی بهره‌برداری از طریق جستجوی محلی است که مورداستفاده قرار می‌گیرد [29]. طراحی یک روش جستجوی محلی کارآمد مهم است. ضمناً در این تحقیق هدف اصلی پیداکردن اولین پاسخ قابل‌قبول با کمتر کردن تعداد نسل‌های موردنیاز فرا ابتکاری است نه حل و یافتن راه‌حل بهینه مسئله کشف نوع مشتری. به‌طورخلاصه در این بخش، یک­سری رویکرد را معرفی می‌کنیم و سپس این رویکردها را ارزیابی می‌کنیم تا یکی از آنها را به‌عنوان رویکرد جستجوی محلی الگوریتم ممتیک انتخاب کنیم.        همان‌طور که در بخش قبل توضیح داده شد، یک راه‌حل  شامل برخی از انواع مشتری است. فرض کنید که راه‌حل   که در آن  یک نوع مشتری است. دیدگاه اصلی جهت یافتن همسایه بهتر برای  است. در ذیل، سه رویکرد مختلف برای جستجوی محلی با توجه به این دیدگاه پیشنهاد شده است. ·       رویکرد اول: همان‌طور که قبلا ذکر شد،  لیستی از برخی محصولات است. در این رویکرد، جایگشت­های دیگر این محصولات را به عنوان  در نظر می‌گیریم. ·       رویکرد دوم: تعداد دوره‌های ناسازگار با  را درنظر می‌گیریم. محصولی که باعث ایجاد بیشترین ناسازگاری شده است را پیدا می‌کنیم. سایر جایگشت های این نوع مشتری را بدون محصولی که باعث ناسازگاری شده را به عنوان  در نظر می‌گیریم. ·       رویکرد سوم: سایر جایگشت های  را ایجاد می‌کنیم، سپس مقدار تابع برازندگی را به ازای همه محاسبه می‌کنیم و بهترین نوع مشتری را به عنوان  معرفی می‌کنیم. 4-       آزمایشات برای ارزیابی، از مجموعۀ داده‌ مربوط به پنج هتل Continental واقع در ایالات‌متحده استفاده شد. این مجموعه داده عمدتاً شامل اطلاعات سفر افرادی است که برای اهداف تجاری اتاق رزرو کرده‌اند. این مجموعه‌داده به‌صورت عمومی در دسترس است و به‌عنوان بنچمارک برای مسئلۀ کشف نوع مشتری استفاده می‌شود. بازه زمانی داده‌ها از 12 مارس 2007 تا 15 آوریل 2007 است که 34 روز را شامل می‌شود [23]. رزروها از طریق کانال‌های مختلفی مانند آژانس‌های مسافرتی، اپراتورهای هتل، بازدیدهای شخصی و وب‌سایت هتل‌ها انجام‌شده است. برای ارزیابی کارایی رویکرد‌های جستجوی محلی خود، سه رویکرد ذکر ‌شده با الگوریتم ممتیک، پیاده‌سازی و روش ژنتیک [19] مقایسه شد. برای هر دو رویکرد (ممتیک و ژنتیک) جمعیت اولیه تصادفی با تعداد 25 ایجاد شد. آزمایش برای نمایش سرعت همگرایی در فاز اولیه (همگرایی جمعیت از راه‌حل‌های غیرقابل‌قبول به راه‌حل‌های قابل‌قبول) است. در این آزمایش هنگامی که اولین راه‌حل قابل‌قبول ایجادشده است، از ادامه کار الگوریتم جلوگیری شد. هر آزمایش 30 بار تکرار شده و میانگین نتایج در جدول (۲) گزارش‌شده است. در ستون «دیتاست» شماره مجموعه داده هتل و در ستون رویکرد، ژنتیک و سه رویکرد پیشنهادی برای همسایگی در ممتیک مشاهده می‌شود. منظور از اندازه راه‌حل، تعداد نوع‌های مشتری موجود در راه‌حل است. همچنین در شکل‌های (2-3) درصد بهبود نسبت به ژنتیک مشاهده می‌شود. همان‌طور که از این شکل‌ها مشخص است، تنها رویکرد سوم می‌تواند میزان همگرایی بهتری در زمینه همسایگی اعمال کند. همچنین برای مقایسه بهتر، میزان شباهت که در تابع برازندگی استفاده و توسط (5) محاسبه می‌شود نیز با دو روش دیگر نیز مقایسه شد که در جدول (۳) قابل مشاهده است. این مقایسه جهت بررسی این موضوع است که آیا ارزش راه‌حل ها در صورت استفاده از همسایگی کمتر می‌شود یا نه. در این جدول با توجه به اینکه میزان شباهت هر دو الگوریتم مشابه بوده­است، هر دو روش را در یک سطر قرار داده­ایم. به این مورد دقت شود که در این تحقیق، میزان برتری الگوریتم ممتیک نسبت به ژنتیک [19] در کم شدن تعداد نسل مورد نیاز برای رسیدن به راه‌حل بوده است. در جدول (۳) روش ID20  در [16] و روش 21RMD در [17] نمایش داده شده است. رویکرد همسایگی باعث کم ارزش‌تر شدن راه‌حل های نهایی نیست. جدول (۲): نمایش تعداد نسل موردنیاز برای ایجاد اولین راه‌حل قابل‌قبول اندازه راه‌حل (8)   دیتاست رویکرد اندازه راه‌حل تعداد نسل هتل ۱ ژنتیک 12.2 98.3 ممتیک، رویکرد اول 12.8 97.9 ممتیک رویکرد دوم 12.6 98.1 ممتیک رویکرد سوم 12.5 82.3 هتل ۲ ژنتیک 12.7 198.8 ممتیک، رویکرد اول 11.8 196.3 ممتیک رویکرد دوم 11.7 197.2 ممتیک رویکرد سوم 11.6 183.2 هتل ۳ ژنتیک 12.6 197.0 ممتیک، رویکرد اول 13.3 196.1 ممتیک رویکرد دوم 13.5 196.8 ممتیک رویکرد سوم 13.6 173.1 هتل ۴ ژنتیک 9.6 115.4 ممتیک، رویکرد اول 10.0 114.3 ممتیک رویکرد دوم 10.3 115.1 ممتیک رویکرد سوم 10.2 100.9 هتل 5 ژنتیک 11.1 71.7 ممتیک، رویکرد اول 10.6 70.9 ممتیک رویکرد دوم 10.7 71.2 ممتیک رویکرد سوم 10.5 68.3 جدول (3): نمایش تعداد نسل موردنیاز برای ایجاد اولین راه‌حل قابل‌قبول اندازه راه‌حل دیتاست روش Log-Value هتل ۱ I.D 2621- RMD 2426- ژنتیک و ممتیک 2095- هتل ۲ I.D 778- RMD 536- ژنتیک و ممتیک 491- هتل ۳ I.D 1569- RMD 1129- ژنتیک و ممتیک 1073- هتل ۴ I.D 616- RMD 401- ژنتیک و ممتیک 352- هتل 5 I.D 406- RMD 370- ژنتیک و ممتیک 339-   شکل (2): درصد بهبود رویکرد‌های همسایگی ممتیک نسبت به ژنتیک در هتل‌های ۱ الی ۳   شکل (3): درصد بهبود رویکرد‌های همسایگی ممتیک نسبت به ژنتیک در هتل‌های ۴ و ۵ 5-       نتیجه‌گیری اگر هر نوع مشتری را به‌عنوان یک لیست ترجیحی از محصولات در نظر بگیریم، کشف انواع مشتری گام ابتدایی برای برآورد تقاضای محصولات و یکی از اولین مراحل استراتژی قیمت‌گذاری است. در صورت استفاده از معاملات فروش و داده‌های موجود بودن محصول، یافتن انواع مشتری با روش‌های فراابتکاری به‌دلیل کمبود داده چالش‌برانگیز است. در برخی از برنامه‌های کاربردی، یافتن اولین راه‌حل قابل‌قبول در یک‌زمان کوتاه چالش‌برانگیزتر از یافتن راه‌حل بهینه است. در این تحقیق برای پیداکردن سریعتر اولین راه‌حل قابل‌قبول در الگوریتم ژنتیک به سراغ الگوریتم ممتیک رفته‌ایم. زیرا با ترکیب این الگوریتم با الگوریتم جستجوی محلی میتوان انتظار داشت که این الگوریتم سریعتر به اولین راه‌حل قابل‌قبول برسد،‌ لذا در این تحقیق سه رویکرد برای جستجوی محلی ارائه کردیم،‌ سپس این سه رویکرد را پیاده‌سازی و با الگوریتم ژنتیک مقایسه کردیم، این مقایسه را با استفاده از داده‌های واقعی پنج هتل انجام داده‌ایم. نتایج مقایسه نشان داد که اگر روند همسایگی به نحوی باشد که تابع برازندگی را به‌سمت نتایج بهتر سوق دهد می‌توان همگرایی سریع‌تری در الگوریتم داشت و سریع­تر به اولین راه‌حل قابل‌قبول مسئله برسیم. همچنین روش پیشنهادی راه‌حل‌هایی با ارزش بالاتر نسبت به روش­های گذشته و هم‌ارزش با روش موجود ارائه می‌دهد و نشان می‌دهد که همسایگی تاثیر منفی بر روی ارزش راه‌حل‌های ارائه شده ندارد. می­توان رویکردهای دیگری را به عنوان همسایگی در نظر گرفت؛ این رویکردها خود می‌توانند الگوریتم‌های فراابتکاری (نظیر PSO) باشد تا بتوان همسایگی بهتری را برای الگوریتم ممتیک به‌دست آورد و ارزش راه‌حل‌های نهایی را بالاتر برد. این موضوع را می‌توان به عنوان پیشنهاد برای ادامه این تحقیق درنظر گرفت. مراجع [1]       K. T. Talluri and G. J. Van Ryzin, The Theory and Practice of Revenue Management, vol. 68. Boston, MA: Springer US, 2004. [2]       P. Liu and S. Smith, “Estimating unconstrained hotel demand based on censored booking data,” Journal of Revenue and …, July 01, 2002. http://link.springer.com/10.1057/palgrave.rpm.5170015 (accessed February 21, 2018). [3]       A. Nikseresht and K. Ziarati, “Estimating True Demand in Airline’s Revenue Management Systems using Observed Sales,” Int. J. Adv. Comput. Sci. Appl., vol. 8, no. 7, pp. 361–369, 2017, doi: 10.14569/ijacsa.2017.080748. [4]       C. Y. Goh, C. Yan, and P. Jaillet, “Estimating Primary Demand in Bike-sharing Systems,” SSRN Electron. J., Jan. 2019, doi: 10.2139/ssrn.3311371. [5]       J. P. Newman, M. E. Ferguson, L. A. Garrow, and T. L. Jacobs, “Estimation of Choice-Based Models Using Sales Data from a Single Firm,” Manuf. Serv. Oper. Manag., vol. 16, no. 2, pp. 184–197, May 2014, doi: 10.1287/msom.2014.0475. [6]       A. Aouad, V. F. Farias, and R. Levi, “Assortment Optimization under Consider-then-Rank Choice Models,” SSRN Electron. J., Jun. 2015, doi: 10.2139/ssrn.2618823. [7]       A. Aouad, V. Farias, R. Levi, and D. Segev, “The approximability of assortment optimization under ranking preferences,” Oper. Res., vol. 66, no. 6, pp. 1661–1669, Nov. 2018, doi: 10.1287/opre.2018.1754. [8]       D. Bertsimas and V. V Mišic, “Data-driven assortment optimization,” Manage. Sci., vol. 1, pp. 1–35, 2015. [9]       S. Jagabathula, “Assortment Optimization Under General Choice,” Ssrn, pp. 1–51, 2014, doi: 10.2139/ssrn.2512831. [10]       S. Jagabathula and P. Rusmevichientong, “A Nonparametric Joint Assortment and Price Choice Model,” Ssrn, no. July, 2013, doi: 10.2139/ssrn.2286923. [11]       G. Gallego, H. Topaloglu, and others, Revenue management and pricing analytics, vol. 209. Springer, 2019. [12]       G. Bitran and R. Caldentey, “An overview of pricing models for revenue management,” Manuf. Serv. Oper. Manag., vol. 5, no. 3, pp. 203–229, 2003. [13]       S. Kunnumkal, “Randomization Approaches for Network Revenue Management with Customer Choice Behavior,” Prod. Oper. Manag., vol. 23, no. 9, pp. 1617–1633, Sep. 2014, doi: 10.1111/poms.12164. [14]       L. Chen and T. Homem-de-Mello, “Mathematical programming models for revenue management under customer choice,” Eur. J. Oper. Res., vol. 203, no. 2, pp. 294–305, Jun. 2010, doi: 10.1016/J.EJOR.2009.07.029. [15]       G. Vulcano, G. van Ryzin, and R. Ratliff, “Estimating Primary Demand for Substitutable Products from Sales Transaction Data,” Ssrn, no. August 2015, 2011, doi: 10.2139/ssrn.1923711. [16]       G. van Ryzin and G. Vulcano, “A Market Discovery Algorithm to Estimate a General Class of Nonparametric Choice Models,” Manage. Sci., vol. 61, no. 2, pp. 281–300, 2015, doi: 10.1287/mnsc.2014.2040. [17]       G. van Ryzin and G. Vulcano, “Technical Note—An Expectation-Maximization Method to Estimate a Rank-Based Choice Model of Demand,” Oper. Res., vol. 65, no. 2, pp. 396–407, 2017, doi: 10.1287/opre.2016.1559. [18]       S. Jagabathula, D. Mitrofanov, and G. Vulcano, “Inferring Consideration Sets from Sales Transaction Data,” SSRN Electron. J., 2019, doi: 10.2139/ssrn.3410019. [19]       M. HajMirzaei, K. Ziarati, and A. Nikseresht, “Discovering customer types using sales transactions and product availability data of 5 hotel datasets with genetic algorithm,” J. Revenue Pricing Manag., 2020, doi: 10.1057/s41272-020-00245-3. [20]       S. Jagabathula and G. Vulcano, “A Partial-order-based Model to Estimate Individual Preferences Using Panel Data,” SSRN Electron. J., no. April, 2017, doi: 10.2139/ssrn.2560994. [21]       H. Lee and Y. Eun, “Discovering heterogeneous consumer groups from sales transaction data,” Eur. J. Oper. Res., vol. 280, no. 1, pp. 338–350, Jan. 2020, doi: 10.1016/J.EJOR.2019.05.043. [22]       M. HajMirzaei, K. Ziarati, and A. Nikseresht, “A customer type discovery algorithm in hotel revenue management systems,” J. Revenue Pricing Manag., 2021, doi: 10.1057/s41272-020-00273-z. [23]       T. Bodea, M. Ferguson, and L. Garrow, “Data Set —Choice-Based Revenue Management: Data from a Major Hotel Chain ,” Manuf. Serv. Oper. Manag., vol. 11, no. 2, pp. 356–361, 2008, doi: 10.1287/msom.1080.0231. [24]       L. Davis, Handbook of genetic algorithms. 1996. [25]       D. H. Wolpert and W. G. Macready, “No free lunch theorems for optimization,” IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 67–82, 1997. [26]       J. C. Culberson, “On the futility of blind search: An algorithmic view of ‘no free lunch,’” Evol. Comput., vol. 6, no. 2, pp. 109–127, 1998. [27]       D. E. Goldberg and S. Voessner, “Optimizing global-local search hybrids.,” in GECCO, 1999, vol. 99, pp. 220–228. [28]       P. Moscato, “On evolution, search, optimization, GAs and martial arts: toward memetic algorithms. California Inst. Technol., Pasadena,” 1989. [29]       N. Krasnogor and J. Smith, “A tutorial for competent memetic algorithms: model, taxonomy, and design issues,” IEEE Trans. Evol. Comput., vol. 9, no. 5, pp. 474–488, 2005. [30]       Wang, C. (2022). Efficient customer segmentation in digital marketing using deep learning with swarm intelligence approach. Information Processing & Management, 59(6), 103085. [31]       Narayana, V. L., Sirisha, S., Divya, G., Pooja, N. L. S., & Nouf, S. A. (2022, March). Mall customer segmentation using machine learning. In 2022 International Conference on Electronics and Renewable Systems (ICEARS) (pp. 1280-1288). IEEE. [32]       Griva, A., Zampou, E., Stavrou, V., Papakiriakopoulos, D., & Doukidis, G. (2023). A two-stage business analytics approach to perform behavioural and geographic customer segmentation using e-commerce delivery data. Journal of Decision Systems, 1-29.   [1]  Revenue Managment [2]  Demand Estimation [3]  Assortment Optimization [4]  Customer Type [5]  Customer Type Discovery [6]  choice-based demand estimation [7]  Metaheuristics [8]  Local Search [9]  Fitness [10]  Mixed-integer program [11]  Expectation maximization [12]  Panel [13]  Expectation maximization [14]  Period [15]  Compatible [16]  Choice-based model [17]  Maximum likelihood estimator [18]  Evolutionary algorithms [19]  Crossover [20]  Independent Demand [21]  Ranked-based Market Discovery