Analyzing Real-time Delivery Policies with Non-Linear Holding Costs

We consider a delivery-dispatch system where orders arrive one by one, they are accumulated for a while and then dispatched as a batch, but get delivered one by one. There are three types of costs: a fixed cost, a delivery cost per unit time spent delivering, and a holding cost. The holding cost is a non-linear function of the time from when an order is placed until it is delivered. Analyzing such a non-linear cost is challenging but necessary due to its practicality. The key idea is to convert the non-linear holding cost into a state-dependent holding cost, i.e., as a function of the number of jobs in hand at a given time, and time-averaged across the delivery process. In this paper, for a fixed-quantity dispatch policy, we illustrate the equivalence of the state-dependent holding cost to the non-linear holding cost via the generalized Little's law in MjG1\ queues. Then, to understand the structure of the optimal real-time dispatch policy, we solve a shortest path problem using arc costs derived in hindsight from a simulation.