Search

We aim to improve the efficiency of a new type of automated storage and retrieval systems (AS/RSs) called multi-control automated storage and retrieval systems (MC-AS/RSs). MC-AS/RSs have multiple storage/retrieval (S/R) machines that operate independently according to storage and retrieval requests. Consequently, MC-AS/RSs can transport loads farther without using human labor, thereby requiring fewer human resources than conventional AS/RSs. However, the structure and control method of AS/RSs are complex because multiple S/R machines must be controlled simultaneously. Therefore, when operating an MC-AS/RS, many factors must be considered, such as the sequence and transport timing. We propose an optimization method using a time-expanded network (TEN) to solve these problems and transport in less time. First, our method models an AS/RS with a TEN to calculate the optimal sequence and conveyance timing while considering the movements of multiple S/R machines. Second, we formulate the operational efficiency of the MC-AS/RS as a problem of minimizing the sum of execution times of requests on the TEN. Finally, we generate the request order necessary for practical use based on the results. The mechanisms implemented to achieve include a generator, optimizer, and scheduler. Our experiments confirm that this method reduces the total execution time of requests compared with other rule-based methods. This method enables us to propose an efficient operation method for AS/RSs with a complex structure of multiple carriers. [ABSTRACT FROM AUTHOR]

Waiting at the right location at the right time can be critically important in certain variants of time-dependent shortest path problems. We investigate the computational complexity of time-dependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomial-time hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary of Contributions: This paper addresses simple yet relevant extensions of a fundamental problem in Operations Research: the Shortest Path Problem (SPP). It considers time-dependent variants of SPP, which can account for changing traffic and/or weather conditions. The first variant that is tackled allows for waiting at certain nodes but at a cost. The second variant instead places a limit on the total waiting. Both variants have applications in transportation, e.g., when it is possible to wait at certain locations if the benefits outweigh the costs. The paper investigates these problems using complexity analysis and algorithm design, both tools from the field of computing. Different cases are considered depending on which of the nodes contribute to the waiting cost or waiting limit (all nodes, all nodes except the origin, a subset of nodes...). The computational complexity of all cases is determined, providing complexity proofs for the variants that are NP-Hard and polynomial time algorithms for the variants that are in P. [ABSTRACT FROM AUTHOR]

• The revenue structure and work schedule difference for two kinds of drivers, freelancers and contractors, are defined. • The drivers' synchronous contractual mode and work schedule choice model is formulated and the solution algorithm is designed. • The numerical studies are conducted to clarify the heterogeneity in working patterns between two kinds of drivers and analyze the equilibrium solutions under different market states in a dual-sourcing market. • The optimal wage strategies are explored via sensitivity analysis under different market states. In the ride-hailing market, the platforms could recruit contractors subject to prescriptive schedules to reduce the labor supply uncertainty and balance the demand and supply, and the drivers are entitled to become a freelancer or a contractor and choose the schedule they would like to provide the service. This paper proposes an analytical framework to capture the drivers' decisions of becoming a freelancer and contractor as well as how to arrange their work schedules in a dual sourcing market. The utility structures for two kinds of drivers, freelancers and contractors, are defined and a time-expanded network is adopted to portray the drivers' work schedule choices. With this setting, the drivers' simultaneous contractual mode and work schedule selection model is formulated and the algorithm is designed. The numerical examples are conducted to investigate the characteristics of the equilibrium solutions. The results show that a dual-sourcing market is always advantageous to contractors and conditionally beneficial to the platform, freelancers and customers. When there is low potential demand, higher fixed salary is preferred for the platform to attract contractor and complement the labor supply. When the market is thriving, the effect of the profits' increment by dual-sourcing is not obvious. This work could provide new insights on how to manage a dual-sourcing market for the platform. [ABSTRACT FROM AUTHOR]

This paper proposed a dynamic traffic assignment method based on the connected transportation system to express the time-varied traffic flows caused by uncertain traffic demand and supply in the real traffic network accurately. In dynamic traffic assignment, because of the cumulative volumes of successive time intervals, a route-based traffic assignment algorithm is used for dynamic traffic assignment in this paper. Besides, a novel shortest path algorithm based actual and artificial link is proposed for the time-expanded network that consists of two kinds of arcs: the actual arc and the artificial one. Then, a simple example is used to illustrate the performance of the proposed method. The computational results show that the novel shortest path algorithm based actual and artificial link could be applied in the time-expanded networks with two types of arcs, and the route-based assignment method could achieve optimal balance solutions under different demand modes.

We introduce an effective and efficient iterative algorithm for solving the continuous-time service network design problem. The algorithm achieves its efficiency by carefully and dynamically refining partially time-expanded network models so that only a small number of small integer programs, defined over these networks, need to be solved. An extensive computational study shows that the algorithm performs well in practice, often using time-expanded network models with size much less than 1% (in terms of number of variables and constraints) of a full time-expanded network model. The algorithm is inspired by and has many similarities to the dynamic discretization discovery algorithm introduced in Boland et al. [Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.], but generates smaller partially time-expanded models, produces high-quality solutions more quickly, and converges more quickly. [ABSTRACT FROM AUTHOR]

• We consider a service network design problem with mixed autonomous fleets. • Our dynamic discretization discovery approach outperforms a commercial solver. • Two relaxation-based enhancements provide exact solutions in reduced runtime. • Heuristic search space restriction quickly provides heuristic solutions. • Case study on real-world network gives insights into usage of AVs and platoons. We consider a service network design problem for the tactical planning of parcel delivery in a city logistics setting. A logistics service provider seeks a repeatable plan to transport commodities from distribution centers on the periphery to inner-city satellites. In a heterogeneous infrastructure, autonomous vehicles in level 4 may only drive in feasible streets but need to be pulled elsewhere by manually operated vehicles in platoons. We formulate an integer program to determine the fleet mix, schedule transportation services, and decide on the routing or outsourcing of commodities. Platooning requires a high level of synchronization between vehicles which demands the time-expanded networks to contain narrow time intervals. Thus, we develop an algorithm based on the dynamic discretization discovery scheme which refines partially time-expanded networks iteratively without having to enumerate the fully time-expanded network a priori. We introduce valid inequalities and provide two enhanced versions of the algorithm that exploit linear relaxations of the problem. Further, we propose heuristic ideas to speed up the search for high-quality solutions. In a computational study, we analyze the efficacy of the algorithm in different versions and observe improvements of computational performance in comparison to a commercial solver. Finally, we solve a case study on a real-world based network to obtain insights into the deployment of a mixed autonomous fleet in an existing heterogeneous infrastructure. [ABSTRACT FROM AUTHOR]

We consider a continuous-time variant of the inventory-routing problem in which the maximum quantity that can delivered to a customer depends on the customer's storage capacity and product inventory at the time of the delivery. We investigate critical components of a dynamic discretization discovery algorithm and demonstrate in an extensive computational study that these components are sufficient to produce provably high-quality, often optimal solutions. [ABSTRACT FROM AUTHOR]

A dynamic network introduced by Ford and Fulkerson is a directed graph in which each arc has a capacity and a transit time. The evacuation problem is one of the fundamental problems in a dynamic network. The goal of this problem is to find the minimum time limit Θ such that we can send all the supplies to the sinks within time Θ. An earliest arrival flow is an optimal flow for the evacuation problem such that the amount of supplies which have reached the sinks is maximized at every time step. It is known that in a dynamic network with multiple sinks, if the sinks have capacities, then an earliest arrival flow does not necessarily exist. In this paper, to cope with this issue, we first introduce a lexicographically optimal earliest arrival flow in a dynamic network with multiple sinks. Then we propose a pseudo‐polynomial‐time algorithm for finding a lexicographically optimal earliest arrival flow. Furthermore, we prove that if the transit time of every arc is zero, then we can find a lexicographically optimal earliest arrival flow in polynomial time. [ABSTRACT FROM AUTHOR]

For less-than-truckload (LTL) freight transportation carriers, as shipment sizes are small relative to trailer capacity, profitability is driven by the ability to load trailers with shipments from multiple customers. However, LTL carriers are facing increased pressure from customers to provide short delivery times, which limits their ability to hold freight, a critical tactic for consolidation. As consolidation requires the coordination of shipment paths in both space and time, shorter delivery times necessitate planning methods that can accurately estimate consolidation opportunities in time. This paper adapts and enhances the dynamic discretization discovery method designed for solving the scheduled service network design problem, defined on an arbitrarily fine discretization of time, to produce exact and heuristic methods for the LTL analog, the continuous time load plan design problem. With instances from the literature and based on data from a U.S. LTL carrier, we provide computational evidence that the algorithm can effectively solve this problem. With an analysis of high-quality solutions to the instances based on LTL carrier data, we derive insights into terminal staffing policies. [ABSTRACT FROM AUTHOR]

In underwater acoustic sensor networks (UASNs), the sensors are deployed at different areas of the ocean, which perform information collection and delay-sensitive routing to the data center for further processing or industrial computing. However, in UASNs, the network states have spatiotemporal characteristics due to tides or autonomous underwater vehicles. To steadily route the traffic especially when the spatiotemporal characteristics of the UASNs are considered, a network architecture with intelligent traffic engineering or routing policies is indispensable. In this paper, we employ software-defined networking (SDN) technology and propose an SDN-enabled distributed architecture for UASNs. Based on the proposed architecture, we propose a scheme DSR-SDN for delay-sensitive spatiotemporal routing in SDN-enabled UASNs. The DSR-SDN includes three phases: First, topology awareness; second, spatiotemporal characteristics estimation; and third, routing computation. Particularly, with SDN features, DSR-SDN provides topology awareness based on a proposed software-defined beaconing scheme. Based on the detected topology, the spatiotemporal characteristics of the network states are estimated based on a proposed SDN-based hierarchical node localizing approach SDN-HL. Lead by the SDN controllers, SDN-HL makes use of the proposed “minimum weighted gap” formulation and Adam algorithm to optimize the localization and builds the indirect links to increase the localization rate. To route the traffic through the network with spatiotemporal characteristics, we adopt the time-expanded network approach, based on which a spatiotemporal route decision can be made before the routing starts. The simulation results demonstrate that the proposed scheme, i.e., DSR-SDN, can conduct accurate spatiotemporal characteristic estimation for the network states and provide delay-sensitive spatiotemporal routing for the sensed data. [ABSTRACT FROM AUTHOR]

Integer programs for solving time-dependent models—models in which decisions have to be made about the times at which activities occur and/or resources are utilized—are pervasive in industry, but are notoriously difficult to solve. In the last few years, interest in the role of discretization in approaches to solve these problems has intensified. One novel paradigm, dynamic discretization discovery, has emerged with the potential to greatly enhance the practical tractability of time-dependent models using integer programming technology. We introduce dynamic discretization discovery, illustrate its use on the traveling salesman problem with time windows, highlight its core principles, and point to opportunities for further research. Relations to other approaches for tackling time-dependent models are also discussed. [ABSTRACT FROM AUTHOR]

• Understand behaviors/competitions of EV/GV drivers in a ride-sourcing market. • Characterize EV/GV drivers' schedules via a time-expanded network. • Introduce an elastic labor supply function for willingness to provide services. • Analyze impacts of electric power supplier on benefits of different stakeholders. • Verify findings with numerical examples on a clock-wise time-expanded network. Recently, electric vehicles (EVs) have been introduced to the ride-sourcing market, raising interesting issues on the interaction between EVs and the ride-sourcing market. This study proposes an analytical framework for understanding drivers' behavior in the ride-sourcing market with both EVs and gasoline vehicles (GVs). A time-expanded network is established to sketch out the schedules of working periods of both EV and GV drivers, and recharging schedules of EV drivers under the user equilibrium. The impacts of operating strategies of ride-sourcing platforms and electrical power suppliers on the benefits of different stakeholders are investigated both analytically and numerically. [ABSTRACT FROM AUTHOR]

Highlights • Routing drones among sailing vessels for the inspection; • Construct a time-expanded network to represent the problem; • Develop a network flow-based formulation; • Develop a Lagrangian relaxation-based method to solve the formulation; • Experimental results based on practical data show that our proposed method can efficiently solve the problem with near-optimal solutions. Abstract The use of drones to monitor the emissions of vessels has recently attracted wide attention because of its great potentials for enforcing regulations in emission control areas (ECAs). Motivated by this potential application, we study how drones can be scheduled to monitor the sailing vessels in ECAs, which is defined as a drone scheduling problem (DSP) in this paper. The objective of the DSP is to design a group of flight tours for drones, including the inspection sequence and timings for the vessels, such that as many vessels as possible can be inspected during a given time period while prioritizing highly weighted vessels for inspection. We show that the DSP can be regarded as a generalized team orienteering problem, which is known to be NP-hard, and deriving solutions for this problem can be more difficult because additional complicated features, such as time-dependent locations, multiple trips for a drone, and multiple stations (or depots), are addressed simultaneously. To overcome these difficulties, we model the dynamics of each sailing vessel using a real-time location function in a deterministic fashion. This approach allows us to approximately represent the problem on a time-expanded network, based on which a network flow-based formulation can be formally developed. To solve this proposed formulation, we further develop a Lagrangian relaxation-based method that can obtain near-optimal solutions for large-scale instances of the problem. Numerical experiments based on practically generated instances with 300 time points and up to 100 vessels are conducted to validate the effectiveness and efficiency of the proposed method. Results show that our method derives tight upper bounds on optimal solutions, and can quickly return good feasible solutions for the tested instances. We also conduct experiments based on realistic tracking data to demonstrate the usefulness of our solutions, including those for the cases considering the uncertainty of vessel locations. [ABSTRACT FROM AUTHOR]

Highlights • Ride-sourcing drivers enjoy flexibility in deciding their work schedules. • This paper models the effect of surge pricing on drivers' work scheduling. • Equilibrium models are formulated based on two hypotheses of labor supply. • The effect of surge pricing is investigated using a bi-level programming framework. • A simple regulation scheme to reduce market power is discussed. Abstract This study proposes equilibrium models under different behavioral assumptions of labor supply in a ride-sourcing market and then investigates the performance of surge pricing. A time-expanded network is first proposed to delineate possible work schedules of drivers. Based on the proposed network, we provide formulations and algorithms for both neoclassical and income-targeting hypotheses to characterize the labor supply of ride-sourcing drivers, i.e., their choices of work hours. We then investigate the impact of surge pricing using a bi-level programming framework, with the lower-level problem capturing the equilibrium work hour choices while the upper-level one representing revenue-maximizing surge pricing. Compared to static pricing, the platform and drivers are found to generally enjoy higher revenue while customers may be made worse off during highly surged periods. Lastly, a simple regulation scheme to reduce market power is discussed. [ABSTRACT FROM AUTHOR]

Consolidation carriers transport shipments that are small relative to trailer capacity. To be cost effective, the carrier must consolidate shipments, which requires coordinating their paths in both space and time; i.e., the carrier must solve a service network design problem. Most service network design models rely on discretization of time-i.e., instead of determining the exact time at which a dispatch should occur, the model determines a time interval during which a dispatch should occur. While the use of time discretization is widespread in service network design models, a fundamental question related to its use has never been answered: Is it possible to produce an optimal continuous-time solution without explicitly modeling each point in time? We answer this question in the affirmative. We develop an iterative refinement algorithm using partially time-expanded networks that solves continuous-time service network design problems. An extensive computational study demonstrates that the algorithm not only is of theoretical interest but also performs well in practice. [ABSTRACT FROM AUTHOR]

Containers are widely used in the shipping industry mainly because of their capability to facilitate multimodal transportation. How to effectively reposition the nonrevenue empty containers is the key to reduce the cost and improve the service in the liner shipping industry. In this paper, we propose a two-stage robust optimization model that takes into account the laden containers routing as well as the empty container repositioning, and define the robustness for this model with uncertainties in the supply and demand of the empty containers. Based on this definition, we present the robust formulations for the uncertainty sets corresponding to the lp-norm, where p = 1, 2, and ∞, and analyze the computational complexities for all of these formulations. The only polynomial-time solvable case corresponds to the l1-norm, which we use to conduct the numerical study. We compare our approach with both the deterministic model and the stochastic model for the same problem in the rolling horizon simulation environment. The computational results establish the potential practical usefulness of the proposed approach. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes a versatile and interactive route planning problem for sightseeing under various conditions based on constraints of required traveling times and total satisfaction of sightseeing activities, which are time-dependent. In general, traveling times among sightseeing places and the satisfactions of activities also change dependent on various conditions such as weather, climate and season. It is important to represent a satisfying route to ensure the large satisfaction even if any assumable condition happens. In order to incorporate the above-mentioned situations, a multi-objective route planning problem is formulated as a network optimization problems based on Time-Expanded Network to represent time-dependent parameters in a static network. Furthermore, an interactive approach based on the Satisficing Trade-Off Method is introduced to transform the multi-objective into the single. In addition, the proposed problem is equivalently transformed into an extended model of network optimization problems by introducing parameters, and the interactive algorithm is developed. [Copyright &y& Elsevier]

Abstract: We study the structure of discrete-time mixed-integer programming (MIP) models for chemical production scheduling. We discuss how chemical manufacturing facilities can be represented as dynamic networks and then converted into time-expanded networks with side constraints. Based on this representation, we show that material balance constraints of the MIP models correspond to generalized flow balances in time-expanded networks. We discuss the implications of conversion coefficients in tasks with multiple inputs and outputs. We also show that assignment constraints lead to side constraints that are equivalent to clique constraints in the time-expanded task-graph of the facility. Finally, we discuss how variable batchsizes lead to fixed charge network structures. [Copyright &y& Elsevier]

• Solve the combined passenger and parcel transportation problem with a mixed fleet. • Formulate the problem as a MILP model based on a multi-layer time-expanded network. • Develop a network decomposition-based math-heuristic to efficiently solve the problem. • Evaluate the model and the algorithm using real-world instances. This study deals with a variant of the vehicle routing problem that aims to design the optimal routes for a mixed fleet of taxis that simultaneously services a given set of passenger and parcel requests. The fleet is composed of electric vehicles and gasoline vehicles. The problem is called combined passenger and parcel transportation problem with a mixed fleet (CPPT-MF). We construct a time-expanded network which is used to model the movements of passengers, parcels and vehicles in space and time. A mixed-integer linear programming model of the problem is developed on the basis of the time-expanded network. A network partitioning-based math-heuristic is proposed to efficiently solve large-scale instances of the problem. The model and the heuristic are evaluated using a set of real-world instances from a taxi company and a set of randomly generated instances. The computational results show that the proposed approach is effective and efficient for solving the CPPT-MF and could facilitate taxi companies with heterogeneous fleets for deciding the routes to simultaneously service passenger and parcel requests. [ABSTRACT FROM AUTHOR]