A new measure of solution quality for combinatorial task assignment problems

摘要

This paper details a new method for measuring the quality of solutions to combinatorial optimization problems in a task assignment and vehicle routing framework. The authors demonstrate that these task assignment problems exhibit an underlying stochastic structure. This structure allows for useful statistical analysis of the problem domain. We are able to numerically recognize problem domains characterized by non-Gaussian distributions and compute a mapping from this non-Gaussian distribution to a Gaussian one. This allows any fractile from the non-Gaussian distribution to be mapped to a Gaussian distribution. Gaussian statistical analysis tools are then used to rate solution quality.