Packing, Pricing and Loading Operations -- Talk by Chris Bayliss Event

Event details

This seminar presents work carried out for an EPSRC funded research project into packing and pricing in the vehicle ferry industry. Vehicle ferries transport commercial and private vehicles. Customers vary according to their vehicle types and willingness to pay. Our initial research focusses on the integration of optimal packing and optimal dynamic pricing for the optimisation of ticket revenues that can be generated from customers that arrive during the selling season. The optimal solution involves a dynamic programming formulation of the pricing problem where the states are all possible mixes of vehicles that can fit onto the ferry under optimal packing. We present results from a analytical optimal formulation of the problem, then provides results for a simulation and heuristic based formulation that admits larger problem sizes and also attains close to optimal revenues. We then describe some of our more recent work in which we address the problem of queue constrained packing under arrival time uncertainty. In this problem vehicles arrive on departure day in a random order. On arrival they are allocated to lanes in the terminal yard before the loading of the vehicle ferry commences. A yard policy governs the terminal lanes that vehicles are parked in. We formulate this problem as a two-stage stochastic program. In the first stage the arrival order is unknown and the objective is to determine a yard policy that will help to minimise the financial penalties due to failing to load vehicles. In the second stage an arrival order is realised and the objective is to resolve the packing problem in order to minimise financial penalties. We solve the first stage for a generated sample of arrival scenarios (uncertainty set) and propose to control risk with a subset size parameter that allows the optimisation to focus on a specified portion of those arrival scenarios. This work investigates maximin and expected operational revenue objective functions for this problem. We propose a novel Sequential Guillotine Cut Knapsack (SGCKS) packing methodology which allows for the terminal lane orders and the reachability of parking space constraints of the real vehicle ferry loading problem. The SGCKS packing methodology is found to obtain small optimality gaps as compared to a lower bound relaxation of the packing problem. An iterative metaheuristic algorithm is developed to solve the operational revenue maximisation problem. Our results indicate that the maximin objective function obtains higher operational revenues in repeat second stage experiments despite the fact that the expected operational revenue formulation provides solutions for the uncertainty set considered in the first stage.