Synchronizing time-dependent transportation services: Reformulation and solution algorithm using quadratic assignment problem

A new modeling framework is developed in this paper to design a class of synchronized transportation services that can be formulated as a time-dependent synchronized service network design problem. The framework is established using a generic network representation for the quadratic assignment problem (QAP). As one of the fundamental combinatorial optimization problems, the QAP was introduced by Koopmans and Beckman (KB-QAP), in 1957, in the context of locating economic activities. Our proposed network-based QAP (NET-QAP) model not only linearizes the KB-QAP model but also generalizes the traditional QAP model as a special case with a symmetric network structure. The NET-QAP is utilized to formulate a time-dependent synchronized service network design problem to obtain an optimal schedule for both inbound and outbound services in a transshipment area, where commodities are collected from origins using the inbound services and distributed to their final destinations using the outbound services (after sorting and storage). From the view of the Gilmore-Lawler Bound (GLB), this paper explores a new branch and bound framework to solve the synchronizing NET-QAP problem. An extended GLB (E-QAP) is adopted in this research as a lower bound estimator for the first-stage assignment costs, based on several relaxed subproblems in the second-stage assignment. Then, the framework can also be applied to estimate the cost of sub-decisions that are involved in making a broader decision-making problem. Numerical experiments are conducted to demonstrate the effectiveness and applicability of the proposed modeling and computational framework.