Abstract
% This is abstract.tex
% DO NOT LaTeX this file directly, see INSTRUCTIONS.
Human-Guided Simple Search (HuGSS) allows a human user to guide a
combinatorial optimization algorithm (COA). We apply HuGSS to
capacitated vehicle routing with time windows (CVRTW)---a common
problem dealing with scheduling multiple deliveries using vehicle
routing. We study whether artificial intelligence heuristics
(computerized algorithms) can replace the human user and which heuristic
performs the best and why.
We program the heuristics in C++, integrate them with the COA and
analyze their performance by running experiments.
The heuristics do not perform on par with human users in HuGSS. HuGSS
performs significantly better than the heuristics at $p = 0.025$. This is an
important finding, as it ensures that human users are actually doing
something ``intelligent.''
Greedy Random (GR) is the top-performing heuristic, significantly better
than all other heuristics at $p = 0.025$. This heuristic is the first
to use infeasible space (temporary use of invalid solutions) as an
optimization technique; GR finds 73.1\% of its improvements from an
initial infeasible move. GR performs well because of factors other
than infeasibility alone. Variants of GR that only make feasible moves
do not have significantly different performance at a 95\% confidence
level.
These heuristics can be integrated into HuGSS itself, placing
higher-level tools at the disposal of human users. The results of this
research can potentially provide significant savings for
industry.
\begin{center}
\textbf{Research Topic Selection}
\end{center}
I started this project during a research program in the summer of 2000. My
mentor presented me with several topics to research and I chose this one
because of its potential to impact the field. Since then, I have
continued the project remotely.
Return to Human-Guided Simple Search