A traveling salesman problem with time windows for the last mile delivery in online shopping

With the fast growth of the parcel volume of online shopping, home delivery (delivering parcels to customers’ homes or workplaces) has accentuated the pressure on last mile delivery actors. Customer pickup, which allows customers to pick up their parcels from shared delivery facilities near them, has become widely popular. This study introduces a novel travelling salesman problem with time windows for the last mile delivery in online shopping. The purpose is to find a minimum cost tour over given customers and/or shared delivery facilities (SDFs) in which unvisited customers are assigned to the SDFs. A general variable neighbourhood search heuristic is developed to solve the problem. Computational results corroborate that the proposed heuristic is competitive relative to well-known algorithms.     

Optimal and Heuristic Facility Phase-out Strategies

This paper presents an efficient branch and bound algorithm and near optimal heuristic algorithms for solving the problem of withdrawing inventory and/or service facilities for a good or service whose overall demand is declining over time. In particular, this paper models the problem faced by a manager who must consider closing up to M initially open and operating support facilities as demand shifts and declines over a T period planning horizon. The criterion is minimization of total estimated discounted costs. The costs considered are the variable operating cost at each facility, the transportation costs between facilities and demand centers, and the costs to operate and close each facility. Computational results are presented for both the optimum finding and heuristic algorithms.     

基于JITD的服务备件二级分销网络集成研究

从供应链集成的角度出发,使用双层规划建立了服务备件二级分销网络的设施选址-运输路线安排-库存控制问题(CLRIP)模型,确定了分销中心的位置、车辆的运输路线等。该模型充分考虑决策部门和顾客双方的利益,针对服务备件的价值高以及服务水平要求高的特点,将按需拉动的准时制配送策略（JITD）应用于分销网络设计中,在降低系统成本的同时,可以大幅度提高配送的准时性和稳定性。设计了该模型的启发式算法,通过算例验证了模型和算法的有效性。研究结果有助于优化服务备件分销网络结构、提高配送准时性和降低物流成本。     

Multi-commodity warehouse location and distribution planning with inventory consideration

We consider the problem of designing a distribution network for a logistics provider that acquires products from multiple facilities and then delivers those products to many retail outlets. Potential locations for consolidation facilities that combine shipments for cost reduction and service improvements are considered. The problem is formulated with direct shipment and consolidation opportunities. A novel mathematical model is derived to solve a complex facility location problem determining: (i) the location and capacity level of warehouses to open; (ii) the distribution route from each production facility to each retailer outlet; and (iii) the quantity of products stocked at each warehouse and retailer. A genetic algorithm and a specific problem heuristic are designed, tested and compared on several realistic scenarios.     

A Heuristic Programming Algorithm for Warehouse Location

A new heuristic programming method of solving a particular type of warehouse location problem is presented. The problem is to allocate K or less facilities to N possible locations so as to service M demand centers at minimum cost. The algorithm presented is suitable for hand calculation of medium-size problems (50 × 50) or when computerized will readily solve large-scale problems of the order of (600 × 600); i.e., 600 demand centers and 600 possible locations.     

Location and allocation of service units on a congested network

We consider the problem of locating facilities and allocating servers on a congested network (LASCN). Demands for service that originate from the nodes are assumed to be Poisson distributed and the servers provide a service time that is exponentially distributed. The objective is to minimize the total cost of the system which includes a fixed installation cost, a variable server cost, a cost associated with travel time and a cost associated with the waiting time in the facility for all the customers. The problem is formulated using non-linear programming and subsequently analyzed. Results for exact and approximate solution approaches are reported. We also show that we can modify the approaches to solve the LASCN with constraints limiting both the travel time to the servers and the waiting time of customers.     

A multi-commodity supply chain design problem

We consider a multi-commodity supply chain design problem in which we need to determine where to locate facilities and how to allocate customers to facilities so as to minimize total costs. The cost associated with each facility exhibits economies of scale. We show that this problem can be formulated as a nonlinear integer program and propose a Lagrangian-relaxation solution algorithm. By exploiting the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer program that must be solved in solving the Lagrangian relaxation subproblems. We also compare our approach with an existing algorithm.     

Modelling and optimisation of a two-server queue with multiple vacations and working breakdowns

This paper presents a steady-state analysis of an M/M/2 queue with heterogeneous servers (Server 1 and Server 2). Server 1 is reliable and may leave for a vacation when the system becomes empty. Sever 2 is unreliable and may break down while serving customers. When a breakdown occurs, Server 2 reduces the service rate rather than halting service. We formulate this queueing model as a quasi birth-and-death (QBD) process, using the matrix geometric method to compute the stationary distribution of system size. We also develop several measures to evaluate the performance of the system. A cost model based on system performance measures is formulated as a heuristic cost optimisation problem subject to stability conditions. A canonical particle swarm optimisation algorithm is used to obtain numerical solutions for the approximate optimal service rates of Server 1 and Server 2. Moreover, we present numerical results showing the effects of various parameters on the approximate optimal service rates as well as a practical example illustrating the application of the proposed model.     

Multi-level supply chain network design with routing

Recently, the multi-level and multi-facility industrial problem in supply chain management (SCM) has been widely investigated. One of the key issues, central to this problem in the current SCM research area is the interdependence among the location of facilities, the allocation of facilities, and the vehicle routing for the supply of raw materials and products. This paper studies the supply chain network design problem, which involves the location of facilities, allocation of facilities, and routing decisions. The proposed problem has some practical applications. For example, it is necessary for third party logistics (3PL) companies to manage the design of the network and to operate vehicle transportation. The purpose of this study is to determine the optimal location, allocation, and routing with minimum cost to the supply chain network. The study proposes two mixed integer programming models, one without routing and one with routing, and a heuristic algorithm based on LP-relaxation in order to solve the model with routing. The results show that a developed heuristic algorithm is able to find a good solution in a reasonable time.     

Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm

The vehicle routing problem (VRP) is a well-known combinatorial optimisation problem and holds a central place in logistics management. Many exact, heuristic and metaheuristic approaches have been proposed to solve VRP. An important variant of the VRP arises when a ?eet of vehicles is fixed and characterised by different capacities for distribution activities. The problem is known as the heterogeneous fixed fleet VRP (HFFVRP). The HFFVRP is a natural generalisation of the VRP with several vehicle types, each type being defined by a capacity, a fixed cost and a cost per distance unit, and can cover more practical situations in transportation. This problem consists of determining a set of vehicle trips of minimum total length in which a set of customers is to be satisfied in the demand constraints using identical vehicles with limited capacity. If open routes instead of closed ones are considered in the HFFVRP, the problem becomes a heterogeneous fixed fleet Open VRP (HFFOVRP) which has numerous applications in industrial and service problems. In this paper, a bone route algorithm which uses the tabu search as an improved procedure is utilised to solve the HFFOVRP. The proposed algorithm was tested empirically on a 24 of generated VRPs, and compared with elite ant system and ant colony system. In all cases, the proposed algorithm finds the best-known solutions within a reasonable time.     

Daily scheduling of caregivers with stochastic times

This paper addresses a daily caregiver scheduling and routing problem arising in home health care or home care service providers. The problem is quite challenging due to its uncertainties in terms of travel and service times derived from changes in road traffic conditions and customer health status in practice. We first model the problem as a stochastic programme with recourse, where the recourse action is to skip customers without services if the caregiver arrives later than their latest starting service time (i.e. hard time window requirements). Then, we formulate the problem as a set partitioning model and solve it with a branch-and-price (B&P) algorithm. Specifically, we devise an effective discrete approximation method to calculate the arrival time distribution of caregivers, incorporate it into a problem-specific label algorithm, and use a removal-and-insertion-based heuristic and the decremental state-space relaxation technique to accelerate the pricing process. Finally, we conduct numerical experiments on randomly generated instances to validate the effectiveness of the discrete approximation method and the proposed B&P algorithm.     

Designing a model for service facility protection with a time horizon based on tri-level programming

ABSTRACT

This study investigates the tri-level location problem of defence facilities with a time horizon. This research focuses on the r-interdiction median model over a finite time horizon. This research aims to protect the service facilities using the defence facilities against the most severe attack scenario of the attacker, so that the system is able to use its maximum power to serve the customers after being damaged. This problem is established on the basis of leader–follower games in the form of defender–attacker–defender. Moreover, attempts are made to make the model more realistic by considering a time horizon. To solve the problem, a combination of a genetic algorithm, simulated annealing and an exact method is used. Comparison of the solution method of the applied metaheuristic algorithm and the exact solution method in a number of small samples indicates the desirable performance of this algorithm in a reasonable time.     

DEALER INVENTORY MANAGEMENT SYSTEMS

This paper presents a model for analyzing inventory control policies for dealers that support the sales and service of manufactured goods. The environment faced by dealers is characterized by multiple stochastic demand classes (prioritized into emergency and regular), a principal source for boui emergency and regular requirements, multiple secondary sources for expedite requirements, and constraints on the lead time and service performance. We are concerned, in particular, with how dealers manage their inventory stockpiles and select expedite sources for replenishment when they have the option of prioritizing customers. The analysis is based on a periodic review, stochastic demand, (s,S) inventory model of dealer stock control. Exact Markov processes and approximate renewal based models are derived based on Cohen, Kleindorfer and Lee [4] and Cohen and Lee [5]. An approximation is used to develop a heuristic algorithm. Extensive numerical testing indicates that the algorithm generates solutions with acceptable cost and service penalties.     

A single-product network design model with lead time and safety stock considerations

Most existing network design and facility location models have focused on the trade-off between the fixed costs of locating facilities and variable transportation costs between facilities and customers. However, operational performance measures such as service levels and lead times are what motivates customers to bring business to a company and should be considered in the design of a distribution network. While some previous work has considered lead times and safety stocks separately, they are closely related in practice, since safety stocks are often set relative to the distribution of demand over the lead time. In this paper we consider a two-stage supply chain with a production facility that replenishes a single product at retailers. The objective is to locate Distribution Centers (DCs) in the network such that the sum of the location and inventory (pipeline and safety stock) costs is minimized. The replenishment lead time at the DCs depends on the volume of flow through the DC. We require the DCs to carry enough safety stock to maintain the prescribed service levels at the retailers they serve. The explicit modeling of the relationship between the flows in the network, lead times and safety stocks allows us to capture the trade-off between them. We develop a Lagrangian heuristic to obtain near-optimal solutions with reasonable computational requirements for large problem instances.     

Applying genetic algorithm to a new location and routing model of hazardous materials

Nowadays – particularly in systems dealing with hazardous materials (HAZMAT) – in addition to minimising the cost of operations in facility location and routing problems, the risk of these operations is considered an important objective. In this paper, a new mathematical model for the location and routing in facilities and disposal sites is proposed. Also, the risk and cost of transporting goods from facilities to customers is considered. The model minimises weighted sum of the cost and risk by answering these questions: (1) where to open the facilities which produce HAZMAT; (2) where to open disposal sites; (3) to which facilities every customer should be assigned; (4) to which disposal site each facility should be assigned; (5) which route a facility should choose to serve the customers; and (6) which route a facility should choose to reach a disposal site. A novel GA is applied to solve the mathematical model. The results show the robustness of GA in terms of finding high-quality non-dominated solutions and running time.     

Assembly line balancing with parallel workstations and dead time

This paper presents a dynamic programming (DP) algorithm for solving an assembly line-balancing )ALB( problem with parallel workstations. Solutions represent a trade-off between the minimum number of stations required to achieve a balance and the cost of installing additional facilities. Both task costs and equipment costs are considered. A second feature of the algorithm is that it takes into account unproductive time during a cycle.

The advantage of the DP approach is that it readily permits the recursive relationship associated with the serial ALB problem to be modified to accommodate the cost of paralleling. Solutions are obtained with an enumeration scheme that exploits known lower bounds. Two examples, and the results from a series of industry-based test problems, are presented to highlight the computations. In general, the algorithm performs well, but runs into trouble when the order strength of the underlying precedence graph is close to one or zero.     

Designing service sectors for daily maintenance operations in a road network

The problem of designing service sectors in a road network for the organisation of route maintenance activities is addressed in this paper. The decisions involve determining the locations of a set of depots and assigning road segments to the selected depots to form service sectors. Routing operations must be taken into consideration while partitioning service sectors in order to precisely evaluate deadhead and required number of vehicles. The problem is thus formulated as a location-arc routing problem and solved by a branch-and-cut algorithm. A three-stage heuristic algorithm with sector design component is developed to solve the medium- and large-sized problems. The computational experiments demonstrate the effectiveness of the heuristic algorithm, and the superiority of the heuristic algorithm to the exact method in terms of some specific partition evaluation criteria.     

Location of congested capacitated facilities with distance-sensitive demand

In this paper we investigate the problem of locating a given number of facilities on a network. Demand generated at a node is distance dependent, i.e., it decreases with an increase in the distance. The facilities can serve no more than a given number of customers, thus they are capacitated and congested when they reach that limit. The objective function is to maximize the demand satisfied by the system given these constraints. An elegant solution is given for the location of one facility. The multiple facility problem is formulated and heuristic algorithms proposed for its solution. Computational experiments are reported.     

Locating service facilities to reduce lost demand

We analyze the problem of locating a set of service facilities on a network when the demand for service is stochastic and congestion may arise at the facilities. We consider two potential sources of lost demand: (i) demand lost due to insufficient coverage; and (ii) demand lost due to congestion. Demand loss due to insufficient coverage arises when a facility is located too far away from customer locations. The amount of demand lost is modeled as an increasing function of the travel distance. The second source of lost demand arises when the queue at a facility becomes too long. It is modeled as the proportion of balking customers in a Markovian queue with a fixed buffer length. The objective is to find the minimum number of facilities, and their locations, so that the amount of demand lost from either source does not exceed certain pre-set levels. After formulating the model, we derive and investigate several different integer programming formulations, focusing in particular on alternative representations of closest assignment constraints. We also investigate a wide variety of heuristic approaches, ranging from simple greedy-type heuristics, to heuristics based on time-limited branch and bound, tabu search, and random adaptive search heuristics. The results of an extensive set of computational experiments are presented and discussed.     

Ant colony optimisation algorithm for distribution-allocation problem in a two-stage supply chain with a fixed transportation charge

In a fixed charge transportation problem, each route is associated with a fixed charge (or a fixed cost) and a transportation cost per unit transported. The presence of the fixed cost makes the problem difficult to solve, thereby requiring the use of heuristic methods. In this paper, an algorithm based on ant colony optimisation is proposed to solve the distribution-allocation problem in a two-stage supply chain with a fixed transportation cost for a route. A numerical study on benchmark problem instances has been carried out. The results obtained for the proposed algorithm have been compared with that for the genetic algorithm-based heuristic currently available in the literature. It is statistically confirmed that the proposed algorithm provides significantly better solutions.