查看更多>>摘要：Due to the growth of e-commerce, promising last-mile delivery options have emerged to manage the rise in delivery frequency and small-volume deliveries. These delivery methods include mobile parcel lockers that are placed by electric vehicles, which enables customers to receive their packages at any time. This study presents a decision support model for enterprises that utilize mobile parcel lockers in last-mile delivery with pick-up and delivery under horizontal collaboration. The model aims to allocate parcel lockers and route the vehicles with the minimum cost, which encompasses the expenses associated with transportation and placement of the lockers, transportation of customer cargo, vehicle utilization, and payment of drivers. We propose an integer linear programming model for the location routing problem. We present an ILP-based decomposition heuristic and an iterative approach to larger-sized practical instances. A numerical analysis is conducted to see the cost and benefit of bilateral and trilateral collaborations in an illustrative case. According to the results, the total cost is reduced by up to 4.52% for companies in the trilateral collaboration scenario with single warehouses, and by up to 7.32% in the trilateral collaboration scenario with multiple warehouses. We examine the large problem sizes of up to 100 nodes to see the performance of the heuristic approaches compared to the model solutions. The two-stage heuristic achieves the optimal solutions for all instances with a node size 50 in a shorter solution time. The iterative approach allows us to deal with the problem complexity of instances with 75 and 100 nodes and yields 0.88% close solutions to the model on average.
查看更多>>摘要：We study the problem of the optimal design of fiber-to-the-home (FTTH) optical access networks. Given a network of nodes and edges rooted at an optical distribution point (ODP) with a given demand for optical fibers at a subset of these nodes, the problem entails finding the optimal placement of splitters, which allows multiple demand points to share a common fiber between ODP and a splitter, such that sum of the costs of the fiber cables and the splitters is minimized. Additionally, it needs to decide on the optimal selection of a cable type of appropriate capacity on each edge of the network to carry the required traffic. The existing literature on FTTH access network design typically assumes the same number of splitting stages for all demand points-specifically, one in case of a single splitting problem (SSP) or two in case of a double splitting problem (DSP). We provide a mixed-integer programming (MIP) formulation of a mixed splitting problem (MSP), wherein some demand points can be served through one stage of splitting, whereas others can be served through two stages of splitting. We further propose several valid inequalities (VIs), with or without a pre-specified template, to strengthen the formulation. Through our computational experiments on large instances, we demonstrate the efficacy of our proposed VIs, which help improve the lower bound of the problem from 79% to 86.9% of the MIP optimal cost, on average. For the special cases of SSP and DSP, we show that our formulation produces much tighter lower bounds compared to the existing formulation in the literature. On top of that, our proposed VIs are comparatively much more effective in tightening the bounds. Specifically, our proposed formulation with our VIs consistently outperforms that available in the literature, being as much as 500 times faster in some instances.
查看更多>>摘要：A deadlock occurs in a network when two or more items prevent each other from moving and are stalled. In a general model, items are stored at vertices and each vertex v has a buffer with b(v) slots. Given a route for each item toward its destination, the Deadlock Safety Problem asks whether the current state is safe, that is, it is possible to deliver each item at its destination, or is bound to deadlock, that is, any sequence of moves will end up with a set of items stalled. While when b ≥ 2 the problem is solvable in polynomial time building upon a nice characterization of YES/NO-instances, it is NP-hard on quite simple graphs as grids when b = 1 and on trees when b ≤ 3. We improve on these results by means of two new tools, weak deadlock sets and wise states. We show that for general networks and b a state that is wise and without weak deadlock sets-this can be recognized in polynomial time-is safe: this is indeed a strengthening of the result for b ≥ 2. We sharpen this result for trees, where we show that a wise state is safe if and only if it has no weak deadlock set. That is interesting in particular in the context of rail transportation where networks are often single-tracked and deadlock detection and avoidance focuses on local sub-networks, mostly with a tree-like structure. We pose some research questions for future investigations.
查看更多>>摘要：We introduce new matheuristic algorithms for the Inventory Routing Problem with unsplit and split deliveries for both Order-Up-to Level and Maximum Level replenishment policies. The first matheuristic is based on the Capacitated Concentrator Location problem. The second is a route-based approach using routes found in other schemes as input, including the ones found in the first matheuristic. We carry out extensive experiments on benchmark instances to understand their effectiveness. The results show that they are effective and require a relatively short computational time.
查看更多>>摘要：In the minimum clique routing problem on cycles mcrpc, we are given a cycle together with a set of demands (weighted terminals pairs) and the goal is to route all the pairs minimizing the maximum weight clique of the intersection graph induced by the routing. The nodes of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work, we are not only interested in the MCRPC but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding terminals. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP-hard even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2-approximation algorithm and a --approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a fixed parameter tractable algorithm for the case of uniform weights, whose parameter is the maximum number of demands for which a demand exists whose terminals alternate in the cycle with the terminals of each of them.
查看更多>>摘要：Wildfire is a global issue that requires contributions from different fields to address its multiple and potentially severe impacts. The subject of this paper is wildfire suppression. In particular, a mixed integer programming (MIP) model is formulated for dispatching, positioning, and routing firefighting resources (e.g., crews and helicopters) in the initial attack. Following the minimum travel time principle, wildfire spread is modeled as the shortest path in a network, as is common in the literature for this type of approach. As for modeling resource movements and attack positions, it is proposed that each type of resource has its own network (e.g., roads) and interaction with the fire spread network. A heuristic, which alternates between MIP (for dispatching and positioning) and shortest path algorithms (for routing) is also conceived, and shown to provide significantly better solutions than solving the complete MIP model. Experiments with data from an actual landscape in Portugal were conducted with pyO3F (a Python framework being developed under the scope of the project "An optimization framework for reducing forest fire"). pyO3F builds the networks of fire and resources from vector and raster files (e.g., land use, altitudes, roads) and parameters from the user (e.g., resolution, fire behavior model). After an optimization approach is applied to a given scenario (characterized by a set of ignition nodes and a wind direction and intensity), pyO3F returns results in text (e.g., the burned area in given instants) and vector files (e.g., fire spread, resources movements, and attacks).
NETL
NSTL
Wiley