On-line scheduling of order picking and delivery with multiple zones and limited vehicle capacity

We consider the on-line business-to-customer (B2C) e-commerce supply chain scheduling problem where customers generate orders on-line that have to be picked from the shelves in a warehouse and delivered to the customers in different zones. The problem is identified as a specific integrated production-delivery problem, named on-line order picking and delivery problem with multiple delivery zones and limited vehicle capacity. The orders are grouped into batches and delivered to their assigned zones by the capacitated vehicles. The objective is to minimize the total cost, which is the sum of the makespan and the delivery cost. We present an on-line 4-competitive algorithm by integrating the existing methods for the on-line integrated production-delivery problem, the on-line batching machine problem, and the on-line order batching problem. Our extensive numerical experiments show that the proposed algorithm is robust and efficient. Moreover, through the comparison with the benchmark, it is demonstrated that the proposed model can lead to a substantial reduction of both the total cost and the delivery cost.