From: jlee@cs.cuhk.hk (Jimmy Ho Man Lee) Newsgroups: comp.constraints Subject: The Mystery Shoppers Problem ... Date: 22 Oct 1996 06:57:58 GMT Organization: Engineering Faculty CUHK Message-ID: <54hr9m$9d@eng-ser1.erg.cuhk.hk> During CP'96, I mentioned a shopper allocation problem and many people are interested in it. It took me a while to clean up the problem and to write it down in a presentable form. I also had to remove real names to protect the company in the problem. So far, we have not been able to come up with any algorithmic solution to the problem. However, our stochastic solver E-GENET is able to find an answer to the problem within 1 second on the average. Please find attached the specification of the problem. I also include one of the answers to the problem generated by E-GENET. There are definitely more than one answer. Perhaps the maintainers of various constraint archives can add this problem to their archives. The usual disclaimer applies. You are welcome to share the problem with other constraint researchers. When you spread the problem, please leave my name in there. If you make any money out of it, don't forget my share! ;-) Your feedback and experiences with the problems are very welcome. Cheers, jim ---------------------------- Mystery Shoppers Problem A well-known cosmetic company wants to evaluate the performance of her saleladies, who station at the company's counters at various department stores in different geographical locations. For this purpose, the company has hired some secret agents to disguise as shoppers to visit the salesladies. The visits must be scheduled in such a way that each saleslady must be visited by shoppers of different varieties and that the visits should be spaced out roughly evenly. Also, shoppers should visit salesladies in different geographic locations. The exact constraints, which ensure the statistical soundness of the project, follow. 1. There are totally 19 outlets to be visited. They are located in 4 geographical regions: - 5 outlets in Area 1: Outlet 1 Outlet 2 Outlet 3 Outlet 4 Outlet 5 - 5 outlets in Area 2: Outlet 6 Outlet 7 Outlet 8 Outlet 9 Outlet 10 - 5 outlets in Area 3: Outlet 11 Outlet 12 Outlet 13 Outlet 14 Outlet 15 - 4 outlets in Area 4: Outlet 16 Outlet 17 Outlet 18 Outlet 19 2. There will be 1 to 4 salesladies in each outlet. Each saleslady will be visited by 4 different shoppers. The frequency of visits to a particular outlet will be the number of salesladies times 4. There are totally 35 salesladies working in all outlets everyday. Therefore, the total number of visits is 140. 3. The shoppers are divided into 4 groups according to age, professions, and etc. Each group has 10 shoppers. Therefore, the total number of shoppers is 40. Therefore, in each group of shoppers, 5 shoppers will perform 3 visits and the other 5 shoppers will perform 4 visits. 4. Each shopper should only visit 1 outlet in each of the 4 areas. 5. All salesladies should be visited 2 times in the first 2 weeks of fieldwork. 6. The total fieldwork period will be 4 weeks. Theoretically, each shopper has to pay 1 visit each week. However, shoppers making 4 visits must have done 2 visits by the end of the second week. Shoppers making 3 visits should have done 1 or 2 visits by the end of the second week. The data of the first 50% visits will be analysed and put in an interim report. 7. Listed below are locations of the 19 outlets and the number of salesladies in that particular outlet. (outlets with * are boutiques) Outlet Number of Salesladies ====== ===================== *Outlet 1 2 Outlet 2 4 Outlet 3 1 Outlet 4 2 Outlet 5 1 Outlet 6 2 Outlet 7 1 Outlet 8 1 Outlet 9 1 *Outlet 10 2 Outlet 11 2 Outlet 12 2 Outlet 13 1 *Outlet 14 2 *Outlet 15 1 Outlet 16 2 Outlet 17 2 Outlet 18 4 Outlet 19 2 ---------------------------- Convention: shoppers 0 - 9 belong to group 1 shoppers 10 - 19 belong to group 2 shoppers 20 - 29 belong to group 3 shoppers 30 - 39 belong to group 4 In each group, the first 5 shoppers make 3 visits and the remaining 5 shoppers make 4 visits. For example, in group 1, shoppers 0 - 4 make 3 visits and shoppers 5 - 9 make 4 visits. Besides, for the salesladies, salesladies 0 - 1 belong to outlet 1 salesladies 2 - 5 belong to outlet 2 salesladies 6 belongs to outlet 3 ... salesladies 33 - 34 belong to outlet 19 shopper[0] visits saleslady[17] in week 2. shopper[0] visits saleslady[2] in week 1. shopper[0] visits saleslady[29] in week 3. shopper[1] visits saleslady[34] in week 3. shopper[1] visits saleslady[11] in week 1. shopper[1] visits saleslady[7] in week 2. shopper[2] visits saleslady[19] in week 0. shopper[2] visits saleslady[33] in week 2. shopper[2] visits saleslady[6] in week 3. shopper[3] visits saleslady[31] in week 3. shopper[3] visits saleslady[13] in week 2. shopper[3] visits saleslady[3] in week 0. shopper[4] visits saleslady[23] in week 0. shopper[4] visits saleslady[4] in week 3. shopper[4] visits saleslady[25] in week 1. shopper[5] visits saleslady[8] in week 1. shopper[5] visits saleslady[16] in week 0. shopper[5] visits saleslady[24] in week 2. shopper[5] visits saleslady[26] in week 3. shopper[6] visits saleslady[1] in week 2. shopper[6] visits saleslady[12] in week 3. shopper[6] visits saleslady[24] in week 0. shopper[6] visits saleslady[32] in week 1. shopper[7] visits saleslady[1] in week 0. shopper[7] visits saleslady[15] in week 1. shopper[7] visits saleslady[24] in week 3. shopper[7] visits saleslady[32] in week 2. shopper[8] visits saleslady[1] in week 1. shopper[8] visits saleslady[15] in week 0. shopper[8] visits saleslady[21] in week 2. shopper[8] visits saleslady[32] in week 3. shopper[9] visits saleslady[3] in week 3. shopper[9] visits saleslady[14] in week 1. shopper[9] visits saleslady[20] in week 0. shopper[9] visits saleslady[25] in week 2. shopper[10] visits saleslady[9] in week 3. shopper[10] visits saleslady[20] in week 2. shopper[10] visits saleslady[27] in week 0. shopper[11] visits saleslady[9] in week 2. shopper[11] visits saleslady[10] in week 0. shopper[11] visits saleslady[28] in week 1. shopper[12] visits saleslady[5] in week 3. shopper[12] visits saleslady[28] in week 2. shopper[12] visits saleslady[17] in week 1. shopper[13] visits saleslady[8] in week 2. shopper[13] visits saleslady[19] in week 1. shopper[13] visits saleslady[26] in week 0. shopper[14] visits saleslady[0] in week 2. shopper[14] visits saleslady[27] in week 1. shopper[14] visits saleslady[12] in week 0. shopper[15] visits saleslady[0] in week 0. shopper[15] visits saleslady[14] in week 3. shopper[15] visits saleslady[24] in week 1. shopper[15] visits saleslady[30] in week 2. shopper[16] visits saleslady[7] in week 0. shopper[16] visits saleslady[12] in week 2. shopper[16] visits saleslady[22] in week 1. shopper[16] visits saleslady[33] in week 3. shopper[17] visits saleslady[6] in week 0. shopper[17] visits saleslady[13] in week 3. shopper[17] visits saleslady[19] in week 2. shopper[17] visits saleslady[26] in week 1. shopper[18] visits saleslady[9] in week 0. shopper[18] visits saleslady[16] in week 2. shopper[18] visits saleslady[23] in week 3. shopper[18] visits saleslady[30] in week 1. shopper[19] visits saleslady[4] in week 2. shopper[19] visits saleslady[11] in week 0. shopper[19] visits saleslady[20] in week 1. shopper[19] visits saleslady[28] in week 3. shopper[20] visits saleslady[30] in week 3. shopper[20] visits saleslady[7] in week 1. shopper[20] visits saleslady[13] in week 0. shopper[21] visits saleslady[33] in week 0. shopper[21] visits saleslady[18] in week 2. shopper[21] visits saleslady[8] in week 3. shopper[22] visits saleslady[22] in week 2. shopper[22] visits saleslady[0] in week 1. shopper[22] visits saleslady[30] in week 0. shopper[23] visits saleslady[4] in week 0. shopper[23] visits saleslady[29] in week 2. shopper[23] visits saleslady[19] in week 3. shopper[24] visits saleslady[0] in week 3. shopper[24] visits saleslady[26] in week 2. shopper[24] visits saleslady[12] in week 1. shopper[25] visits saleslady[5] in week 2. shopper[25] visits saleslady[16] in week 3. shopper[25] visits saleslady[21] in week 1. shopper[25] visits saleslady[25] in week 0. shopper[26] visits saleslady[1] in week 3. shopper[26] visits saleslady[13] in week 1. shopper[26] visits saleslady[22] in week 0. shopper[26] visits saleslady[31] in week 2. shopper[27] visits saleslady[5] in week 1. shopper[27] visits saleslady[11] in week 3. shopper[27] visits saleslady[23] in week 2. shopper[27] visits saleslady[32] in week 0. shopper[28] visits saleslady[4] in week 1. shopper[28] visits saleslady[10] in week 2. shopper[28] visits saleslady[17] in week 0. shopper[28] visits saleslady[25] in week 3. shopper[29] visits saleslady[8] in week 0. shopper[29] visits saleslady[14] in week 2. shopper[29] visits saleslady[18] in week 3. shopper[29] visits saleslady[34] in week 1. shopper[30] visits saleslady[29] in week 1. shopper[30] visits saleslady[2] in week 3. shopper[30] visits saleslady[11] in week 2. shopper[31] visits saleslady[31] in week 1. shopper[31] visits saleslady[2] in week 0. shopper[31] visits saleslady[21] in week 3. shopper[32] visits saleslady[7] in week 3. shopper[32] visits saleslady[16] in week 1. shopper[32] visits saleslady[34] in week 0. shopper[33] visits saleslady[27] in week 3. shopper[33] visits saleslady[23] in week 1. shopper[33] visits saleslady[5] in week 0. shopper[34] visits saleslady[6] in week 2. shopper[34] visits saleslady[33] in week 1. shopper[34] visits saleslady[18] in week 0. shopper[35] visits saleslady[9] in week 1. shopper[35] visits saleslady[14] in week 0. shopper[35] visits saleslady[22] in week 3. shopper[35] visits saleslady[34] in week 2. shopper[36] visits saleslady[6] in week 1. shopper[36] visits saleslady[15] in week 3. shopper[36] visits saleslady[21] in week 0. shopper[36] visits saleslady[27] in week 2. shopper[37] visits saleslady[2] in week 2. shopper[37] visits saleslady[10] in week 3. shopper[37] visits saleslady[18] in week 1. shopper[37] visits saleslady[29] in week 0. shopper[38] visits saleslady[3] in week 1. shopper[38] visits saleslady[15] in week 2. shopper[38] visits saleslady[20] in week 3. shopper[38] visits saleslady[28] in week 0. shopper[39] visits saleslady[3] in week 2. shopper[39] visits saleslady[10] in week 1. shopper[39] visits saleslady[17] in week 3. shopper[39] visits saleslady[31] in week 0.