Optimization Models For Transport And Service Scheduling

Optimization Models for Transport and Service Scheduling

This dissertation focuses on service scheduling and transshipment problems. The study of service scheduling is motivated by decisions facing service planners, who must inspect and maintain geographically dispersed infrastructure facilities. We study the problem of deciding which operations a service unit must perform at each customer location, given the sequence in which the unit periodically visits these locations. Each customer requires multiple service operations, and each operation has a time-varying completion or penalty cost that depends on the previous service time. The goal is to schedule the service start time for each customer and select the operations to perform so as to minimize the total completion cost. We first discuss how to solve a special case of this problem in which each site is visited only once per service cycle. We formulate this problem as a discrete time indexed network flow problem and prove that it is NP-hard in the ordinary sense. Then, we represent the problem as a multidimensional shortest path problem with path-dependent arc lengths. In this structure, arc costs depend on the total time spent for all customers. The resulting formulation is solvable via algorithms that have pseudo-polynomial run times. Computational results show that the shortest path approach outperformed the general network flow model. We then analyze the general case of this problem, in which each site can be visited more than once and prove that the problem is NP-Hard in the strong sense. We discuss the valid cuts and describe the preprocessor that reduces the problem size. Next, we examine an application to the general case of the problem and develop a fast and effective heuristic procedure that repeatedly applies the shortest path approach to subsequences that do not visit any customer more than once. Computational results for several problem instances show that the proposed heuristic identifies near optimal results very quickly, whereas a general purpose integer-programming solver (CPLEX) is not able to find an optimal solution even after many hours of computational time. Then we focus on techniques such as problem reduction, branching variables, and subdividing problem to smaller problems to get better solution times for the actual problem. Computational results show that these techniques can improve solution times substantially. Finally, we study a transshipment problem, in which the shipments need to be transported from their origin to destination and are subject to the logical and physical transportation network on which they rely. We consider a space-time network that allows one to formulate the problem as a multi-commodity network flow problem with additional side constraints and show the complexity results. We propose alternative models and propose algorithms for lower and upper bound calculations.

Multidisciplinary Approach in Research Area (Volume-11)

Advances in Urban Engineering and Management Science Volume 1

Advances in Urban Engineering and Management Science contains the selected papers resulting from the 2022 3rd International Conference on Urban Engineering and Management Science (ICUEMS 2022). Covering a wide range of topics, the Proceedings of ICUEMS 2022 presents the latest developments in: (i) Architecture and Urban Planning (Architectural design and its theory, Urban planning and design, Building technology science, Urban protection and regeneration, Urban development strategy, Ecological construction and intelligent control, Sustainable infrastructure); (ii) Logistics and supply chain management (Warehousing and distribution, Logistics outsourcing, Logistics automation, Production and material flow, Supply chain management technology, Supply chain risk management, Global service supply chain management, Supply Chain Planning and Inventory Management, Coordination and collaboration of supply chain networks, Governance and regulatory aspects affecting supply chain management); (iii) Urban traffic management (Smart grid management, Belt and Road Development, Intelligent traffic analysis and planning management, Big data and transportation management). The Proceedings of ICUEMS 2022 will be useful to professionals, academics, and Ph.D. students interested in the above-mentioned fields. Emphasis was put on basic methodologies, scientific development and engineering applications. ICUEMS 2022 is to provide a platform for experts, scholars, engineers and technical researchers engaged in the related fields of urban engineering management to share scientific research achievements and cutting-edge technologies, understand academic development trends, broaden research ideas, strengthen academic research and discussion, and promote the industrialization cooperation of academic achievements. Experts, scholars, business people and other relevant personnel from universities and research institutions at home and abroad are cordially invited to attend and exchange.