|
Optimization benchmark problem for operational planning
and scheduling in an automatic picking system (Ver. 1)
This is old version. The latest version is available from P3 (Ver. 2). Summary
Automatic picking system is one of examples of logistic devices which assort products.
In the automatic picking system, as shown in Figs. 1 and 2, the products are assorted based on the given assortment demands.
In order to obtain an optimal operational plan, the products assignment problem to the lanes and the scheduling problem to determine output schedules of the products from the lanes and a work order of each assortment demand have to be considered simultaneously.
This benchmark problem provides two types of operational planning problems which are labeled "00" and "01".
The specific formulation is given in the references [3] and [4].
 Fig. 1: Automatic picking system [1] (the characters in the figure are written in Japanese)  Fig. 2: Example of delivery demands [1] (the characters in the figure are written in Japanese) Class and scale (in the case of the problem 00)
- Class: Discrete nonlinear optimization problem
- Number of decision variables: 925,500 (Continuous: 0, Discrete: 925,500)
- Number of inequality constraints: 89,075 (Linear: 100, Nonlinear: 88,975)
- Number of equality constraints: 19,100 (Linear: 10,100, Nonlinear: 9,000)
Known Feasible Solutions (OFV is objective function value. Sol. is solution.)
| Method |
OFV |
Constraint violations |
Ref. |
Reporter |
Sol. |
| Total |
Tolerance |
| Constraint programming |
4149.5 |
0 |
1.0 × 10-10 |
[5] |
T. Miyamoto |
Sol.† (Problem 00) |
| Constraint programming |
4047.0 |
0 |
1.0 × 10-10 |
[5] |
T. Miyamoto |
Sol.† (Problem 01) |
| — |
4206.0 |
0 |
0 |
— |
— |
Sol.† (Problem 00) |
| — |
4159.0 |
0 |
0 |
— |
— |
Sol.† (Problem 01) |
†Decompress the obtained file. Replace the decompressed text files by "P3_solution_y.txt" and "P3_data.csv" in the source code.
Source code
P3-1.zip (C/C++) — See "Readme.txt" in order to know how to use.
References
| [1] |
Investigating R&D committee on new development of computational intelligence techniques and their applications to industrial systems: "Optimization benchmark problems for industrial applications", IEEJ Tech. Rep., No. 1287, Section 3.4 (2013) [in Japanese] |
| [2] |
H. Iima and Y. Kawano: "Operational planning and scheduling benchmark problem in an automatic picking systems", Proc. of the 2014 Annual Meeting on the Institute of Electrical Engineers of Japan, Vol. 4, 4-S21(17)–(20) (2014) [in Japanese] |
| [3] |
H. Iima, Y. Koguma, and Y. Kawano: "Operational planning and scheduling benchmark problem in an automatic picking system for metaheuristics", Proc. of Schduling Symposium 2014, pp. 201–206 (2014) [in Japanese] |
| [4] |
H. Iima, Y. Kawano, and Y. Koguma: "Operational planning and scheduling problem in an automatic picking system as a benchmark", Proc. of the first IEEJ International Workshop on Sensing, Actuation, and Motion Control (SAMCON2015), IS1-2 (2015) |
| [5] |
T. Miyamoto, K. Mori, S. Kitamura, and Y. Izui: "Constraint programming model for operational planning and scheduling problem in automatic picking system", Proc. of International Symposium on Scheduling 2015, pp. 163–168 (2015) |
Change log
- Sept. 29th, 2015: A new solution is added to Known Feasible Solutions.
- June 5th, 2015: The bibliographical data of the reference [4] is updated.
- Dec. 3rd, 2014: English page is released.
- Dec. 1st, 2014: The source code is updated based on the reference [3].
- July 18th, 2014: The source code based on the reference [2] is released.
|
|
|