穩健共享停車位規劃問題(Robust Shared Parking Space Scheduling Problem)是共享停車位規劃問題(Shared Parking Space Scheduling Problem)的延伸問題。停車位共享(Parking Space Sharing)的概念，能利用私有車位解決停車位不足的問題。而穩健共享停車位規劃問題則是考慮實際狀況下，增加使用者離開時間為不確定之因素，利用穩健最佳化的設計，在最差狀況情境(worst-case scenario)下，所提出的穩健規劃也能獲得最多的收益。
本研究可以分為三個階段，首先界定研究的範圍與目的，接著完整定義此問題，以背包問題(Knapsack Problem, KP)為基礎，利用穩健最佳化(Robust Optimization)的設計，建立本研究問題之數學規劃模型，最後參考相關文獻，以模擬退火法(Simulated Annealing, SA)為基礎，發展能有效求解此問題之演算法。為了驗證演算法之效果，本研究建立一測試題庫，進行不同類型題目的測試與分析，進而提出結論與建議。

The Robust Shared Parking Space Scheduling Problem is one of the extensions of Shared Parking Space Scheduling Problem. Using the concept of “Parking Space Sharing”, private parking spaces can be utilized to satisfy the excess demand. The Robust Shared Parking Space Scheduling Problem considers a more practical issue of uncertainty in the departure time of users. By using Robust Optimization, the proposed robust scheduling can obtain maximum profit under the worst-case scenario.
Our research can be divided into three stages. We first defined the scope and objectives of this research. In the second stage, we defined the problem and developed a mathematical model for the problem based on the Knapsack Problem (KP) with Robust Optimization. In the last stage, we developed an algorithm for the Robust Shared Parking Space Scheduling Problem based on Simulated Annealing (SA).
A set of instances was created to test the applicability and the efficiency of the proposed meta-heuristic. Conclusions and suggestions are drawn based on the results of these computational experiments.

Atabakhsh, H. (1991). A survey of constraint based scheduling systems using an artificial intelligence approach. Artificial Intelligence in Engineering, 6(2), 58-73.
Bai, D., Carpenter, T., & Mulvey, J. (1997). Making a case for robust optimization models. Management science, 43(7), 895-907.
Baker, K. R. (1974). Introduction to sequencing and scheduling (Vol. 15): Wiley New York.
Bean, J. C. (1984). Technical Note—A Langrangian Algorithm for the Multiple Choice Integer Program. Operations Research, 32(5), 1185-1193.
Bellman, R. (1956). Dynamic Programming and Lagrange Multipliers. Proceedings of the National Academy of Sciences of the United States of America, 42(10), 767-769.
Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. Princeton series in applied mathematics: Princeton University Press Princeton.
Blum, C., & Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys (CSUR), 35(3), 268-308.
Brucker, P., & Kravchenko, S. A. (2008). Scheduling jobs with equal processing times and time windows on identical parallel machines. Journal of Scheduling, 11(4), 229-237.
Butler, R., Ammons, J., & Sokol, J. (2003). A robust optimization model for strategic production and distribution planning for a new product. University of Central Florida, Orlando.
Cheng, T., & Diamond, J. (1995). Scheduling two job classes on parallel machines. IIE transactions, 27(5), 689-693.
Dantzig, G. B. (1957). Discrete-Variable Extremum Problems. Operations Research, 5(2), 266-288. doi: doi:10.1287/opre.5.2.266
Dantzig, G. B. (1963). Linear programming and its extensions: Princeton University Press, Princeton, NJ.
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 26(1), 29-41.
Fisher, M. L. (2004). The Lagrangian relaxation method for solving integer programming problems. Management science, 50(12_supplement), 1861-1871.
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Goerigk, M., Gupta, M., Ide, J., Schobel, A., & Sen, S. (2015). The robust knapsack problem with queries. Computers & Operations Research, 55, 12-22.
Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3(2), 95-99.
Held, M., & Karp, R. (1962). A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210. doi: 10.1137/0110015
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems: Springer.
Kennedy, J. (2010). Particle swarm optimization Encyclopedia of Machine Learning (pp. 760-766): Springer.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simmulated annealing. science, 220(4598), 671-680.
Krishnamoorthy, M., Ernst, A., & Baatar, D. (2012). Algorithms for large scale shift minimisation personnel task scheduling problems. European Journal of Operational Research, 219(1), 34-48.
Lapegue, T., Bellenguez-Morineau, O., & Prot, D. (2013). A constraint-based approach for the shift design personnel task scheduling problem with equity. Computers & Operations Research, 40(10), 2450-2465.
Lawler, E. L., & Wood, D. E. (1966). Branch-and-Bound Methods: A Survey. Operations Research, 14(4), 699-719. doi: doi:10.1287/opre.14.4.699
Li, K., Yang, S.-L., & Ma, H.-W. (2011). A simulated annealing approach to minimize the maximum lateness on uniform parallel machines. Mathematical and Computer Modelling, 53(5), 854-860.
Lin, S.-W., & Ying, K.-C. (2014). Minimizing shifts for personnel task scheduling problems: A three-phase algorithm. European Journal of Operational Research, 237(1), 323-334.
Lo, Z.-P., & Bavarian, B. (1992). Optimization of job scheduling on parallel machines by simulated annealing algorithms. Expert Systems with applications, 4(3), 323-328.
Low, C. (2005). Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers & Operations Research, 32(8), 2013-2025.
Lu, C.-C., & Sheu, J.-B. (2013). Robust vertex p-center model for locating urgent relief distribution centers. Computers & Operations Research, 40(8), 2128-2137.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1087-1092.
Monaci, M., Pferschy, U., & Serafini, P. (2013). Exact solution of the robust knapsack problem. Computers & Operations Research, 40(11), 2625-2631.
Mulvey, J. M., & Vladimirou, H. (1991). Solving multistage stochastic networks: An application of scenario aggregation. Networks, 21(6), 619-643.
Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems: Springer.
Rajendran, C., & Holthaus, O. (1999). A comparative study of dispatching rules in dynamic flowshops and jobshops. European Journal of Operational Research, 116(1), 156-170.
Rambod, M., & Rezaeian, J. (2014). Robust meta-heuristics implementation for unrelated parallel machines scheduling problem with rework processes and machine eligibility restrictions. Computers & Industrial Engineering, 77, 15-28.
Sahni, S. (1975). Approximate algorithms for the 0/1 knapsack problem. Journal of the ACM (JACM), 22(1), 115-124.
Smet, P., Wauters, T., Mihaylov, M., & Vanden Berghe, G. (2014). The shift minimisation personnel task scheduling problem: a new hybrid approach and computational insights. Omega, 46, 64-73.
Toth, P., & Martello, S. (1990). Knapsack Problems: Algorithms and Computer Implementations. Discrete Mathematics and Optimization. Wiley.
Woeginger, G. J. (2003). Exact algorithms for NP-hard problems: A survey Combinatorial Optimization—Eureka, You Shrink! (pp. 185-207): Springer.
Yang, T. (2009). An evolutionary simulation–optimization approach in solving parallel-machine scheduling problems–A case study. Computers & Industrial Engineering, 56(3), 1126-1136.