Stochastic Dynamic Optimization

In the second term of the MRes we have been tasked to write two research topics based on talks we were given just after Christmas. I chose to write my first shorter report on stochastic dynamic optimization. I hope to explain a little about what I looked into, and what my report was about…

Queuing is something that all of us experience on a daily basis. It can be frustrating when we are faced with long queues that are not worth the wait and we may question why we bothered queuing up in the first place. This was first considered in the literature during the 1960s when thinking about how we could reduce queues in all walks of life such as at a cab stand or when hiring industrial equipment.

The method in which I will consider this is when we either have the option to assign an arrival into a queue, or to send them away when they first arrive into the system. This deviates slightly from traditional queuing theory where we consider how we can serve every single individual and this is an important distinction. There are two contrasting ways in which this can be thought of: selfish and social policies. With a selfish policy the individual is only concerned with maximizing their own expected profit, and does not take into account anybody else. This is in contrast to a social policy where there is some authority organizing the queue in order to maximize the expected profit of the entire population as a whole.

It is a relatively simple concept, but in fact it can spring surprising results. For example, what may not be instinctive is that in fact to increase the reward of the whole, we must shorten the length the queue can build up before turning new arrivals away. Thus the point of how one would go about implementing these in practice is not a simple task. One of the ideas first proposed in the literature is finding a toll that must be paid in order to join this queue. This has already been implemented in some systems such as for example when booking a taxi we have surge prices when demand is high, and cheaper prices when demand is low. Doing this helps to even out the arrival of customers in order to maximize the profit by the operator. For simple queues we can in fact mathematically calculate how we would go about doing this in order to push an individuals selfish policy to match up with the social policy for the system. However, this can lead into ethical complications when we are looking systems that represent a basic human need such as the distribution of aid or other essential supplies that are of immediate need for vulnerable people. This can lead into many different considerations and as such I did not go into this in my report but it is an interesting point and important to think about.

I instead was focused on the construction of the social and selfish policies for a general model of queuing. The methodology of this quickly becomes complicated due to the large number of scenarios we can find ourselves in. Thus I explained how we can come up with this directly for the most basic form of queue with one server at one facility and we can either choose to allow an arrival to join the back of the queue, or force them to leave with nothing (called balking). I then referred to methods that others have introduced in order to be able to solve more complicated and general methods with the help of computers. However, these quickly become infeasible when dealing with anything other than small toy problems and thus we must look at heuristics that can approximate the solution rather than solving it exactly.