Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design

Maritime cabotage is a legislation published by a particular coastal country, which is used to conduct the cargo transportation between its two domestic ports. This paper proposes a two-phase mathematical programming model to formulate the liner hub-and-spoke shipping network design problem subject to the maritime cabotage legislations, i.e., the hub location and feeder allocation problem for phase I and the ship route design with ship fleet deployment problem for phase II. The problem in phase I is formulated as a mixed-integer linear programming model. By developing a hub port expanding technique, the problem in phase II is formulated as a vehicle routing problem with pickup and delivery. A Lagrangian relaxation based solution method is proposed to solve it. Numerical implementations based on the Asia–Europe–Oceania shipping services are carried out to account for the impact analysis of the maritime cabotage legislations on liner hub-and-spoke shipping network design problem.     

On solving the discrete location problems when the facilities are prone to failure

The classical discrete location problem is extended here, where the candidate facilities are subject to failure. The unreliable location problem is defined by introducing the probability that a facility may become inactive. The formulation and the solution procedure have been motivated by an application to model and solve a large size problem for locating base stations in a cellular communication network. We formulate the unreliable discrete location problems as 0–1 integer programming models, and implement an enhanced dual-based solution method to determine locations of these facilities to minimize the sum of fixed cost and expected operating (transportation) cost. Computational tests of some well-known problems have shown that the heuristic is efficient and effective for solving these unreliable location problems.     

The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search

The Team Orienteering Problem (TOP) is a known NP-hard problem that typically arises in vehicle routing and production scheduling contexts. In this paper we introduce a new solution method to solve the TOP with hard Time Window constraints (TOPTW). We propose a Variable Neighborhood Search (VNS) procedure based on the idea of exploring, most of the time, granular instead of complete neighborhoods in order to improve the algorithm’s efficiency without loosing effectiveness. The method provides a general way to deal with granularity for those routing problems based on profits and complicated by time constraints. Extensive computational results are reported on standard benchmark instances. Performance of the proposed algorithm is compared to optimal solution values, when available, or to best known solution values obtained by state-of-the-art algorithms. The method comes out to be, on average, quite effective allowing to improve the best know values for 25 test instances.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

City-courier routing and scheduling problems

This research seeks to propose innovative routing and scheduling strategies to help city couriers reduce operating costs and enhance service level. The strategies are realized by constructing a new type of routing and scheduling problem. The problem directly takes into account the inherent physical and operating constraints associated with riding in city distribution networks, which makes the problem involve multiple objectives and visiting specified nodes and arcs. Through network transformations, this study first formulates the city-courier routing and scheduling problem as a multi-objective multiple traveling salesman problem with strict time windows (MOMTSPSTW) that is NP-hard and new to the literature, and then proposes a multi-objective Scatter Search framework that seeks to find the set of Pareto-optimal solutions to the problem. Various new and improved sub-procedures are embedded in the solution framework. This is followed by an empirical study that shows and analyzes the results of applying the proposed method to a real-life city-courier routing and scheduling problem.     

A heuristic algorithm for constrained multi-source Weber problem – The variational inequality approach

For solving the well-known multi-source Weber problem (MWP), each iteration of the heuristic alternate location–allocation algorithm consists of a location phase and an allocation phase. The task of the location phase is to solve finitely many single-source Weber problems (SWP), which are reduced by the heuristic of nearest center reclassification for the customers in the previous allocation phase. This paper considers the more general and practical case – the MWP with constraints (CMWP). In particular, a variational inequality approach is contributed to solving the involved constrained SWP (CSWP), and thus a new heuristic algorithm for CMWP is presented. The involved CSWP in the location phases are reformulated into some linear variational inequalities, whose special structures lead to a new projection–contraction (PC) method. Global convergence of the PC method is proved under mild assumptions. The new heuristic algorithm using the PC method in the location phases approaches to the heuristic solution of CMWP efficiently, which is verified by the preliminary numerical results reported in this paper.     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

Competitive facility location on decentralized supply chains

This paper addresses a novel competitive facility location problem about a firm that intends to enter an existing decentralized supply chain comprised of three tiers of players with competition: manufacturers, retailers and consumers. It first proposes a variational inequality for the supply chain network equilibrium model with production capacity constraints, and then employs the logarithmic-quadratic proximal prediction–correction method as a solution algorithm. Based on this model, this paper develops a generic mathematical program with equilibrium constraints for the competitive facility location problem, which can simultaneously determine facility locations of the entering firm and the production levels of these facilities so as to optimize an objective. Subsequently, a hybrid genetic algorithm that incorporates with the logarithmic-quadratic proximal prediction–correction method is developed for solving the proposed mathematical program with an equilibrium constraint. Finally, this paper carries out some numerical examples to evaluate proposed models and solution algorithms.     

A new evaluation method based on D–S generalized fuzzy soft sets and its application in medical diagnosis problem

Soft set theory, initiated by Molodtsov, is a general mathematical tool for dealing with uncertain problems. In this paper, we first point out that the similarity measure in a previous paper by Majumdar and Samanta [P. Majumdar, S.K. Samanta, Generalized fuzzy soft sets, Comput. Math. Appl. 59 (2010) 1425–1432] is limited by two counterexamples. To deal with the problems of subjective evaluation and uncertain knowledge, this paper proposes the concept of D–S generalized fuzzy soft sets by combining Dempster–Shafer theory of evidence and generalized fuzzy soft sets. We study some of its operations and basic properties, and the relationship between generalized fuzzy soft sets and D–S generalized fuzzy soft sets are introduced. Then we propose the concept of the similarity between two D–S generalized fuzzy soft sets. At last, we present a new method of evaluation based on D–S generalized fuzzy soft sets and apply it into a medical diagnosis problem.     

A method for solving to optimality uncapacitated location problems

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, thep-median problem and the fixed-chargep-median problem. Computational results are given for problems of up to the size 200 customers ×200 potential facility sites.     

A Particle Swarm Optimization Algorithm with Path Relinking for the Location Routing Problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for solving successfully one of the most popular logistics management problems, the location routing problem (LRP). The proposed algorithm for the solution of the location routing problem, the hybrid particle swarm optimization (HybPSO-LRP), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search – greedy randomized adaptive search procedure (MPNS-GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is tested on a set of benchmark instances. The results of the algorithm are very satisfactory for these instances and for six of them a new best solution has been found.      

Hybrid Laplace transform-finite element method to a generalized electromagneto-thermoelastic problem

A finite element method based on the Laplace transform technique is developed for a two-dimensional problem in electromagneto-thermoelasticity. The problem is in the context of the following generalized thermoelasticity theories: Lord–Shulman’s, Green–Lindsay’s, the Chandrasekharaiah–Tzou, as well as the dynamic coupled theory. The Laplace transform method is applied to the time domain and the resulting equations are discretized using the finite element method. The inversion process is carried out using a numerical method based on a Fourier series expansions. Numerical results compared with those given in literature prove the good performance of the used method. It is demonstrated that the Chandrasekharaiah–Tzou theory can be considered as an extension of Lord–Shulman’s, and the generalized heat conduction mechanism is completely different from the classical Fourier’s in essence.     

Generalized biorthogonal bases and tridiagonalisation of matrices

Summary. In connection with the breakdown problem of the Lanczos algorithm a theory of generalized biorthogonal bases is developed. The connection between the generalized biorthogonal bases of Krylov chains and look-ahead Lanczos recursions is worked out in detail. It is shown how generalized biorthogonal bases with “antidiagonal blocks” can be constructed with small computational effort. Finally a special look-ahead Lanczos algorithm is derived which requires minimal computational effort and storage. Received September 21, 1995 / Revised version received August 12, 1996     

On the generalized directed rural postman problem

The generalized directed rural postman problem (GDRPP) is a generic type of arc routing problem. In the present paper, it is described how many types of practically relevant single-vehicle routing problems can be modelled as GDRPPs. This demonstrates the versatility of the GDRPP and its importance as a unified model for postman problems. In addition, an exact and a heuristic solution method are presented. Computational experiments using two large sets of benchmark instances are performed. The results show high solution quality and thus demonstrate the practical usefulness of the approach.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

Multi-mode project payment scheduling problems with bonus–penalty structure

This paper involves the multi-mode project payment scheduling problem with bonus–penalty structure where activities can be performed with several modes and a bonus–penalty structure exists at the deadline of the project. In the problem the decisions on when to schedule events and payments, the magnitude of each payment, and the performing mode of each activity need to be optimized. A two-module simulated annealing heuristic is proposed to solve the mixed integer non-linear programming models for the contractor and the client, and a satisfactory solution, which consists of payment event set, event schedule, and payment amount set, may be found through iterations between the heuristic’s two modules. The profits of the two parties of the contract are changed significantly by the bonus–penalty structure and the structure may be considered as a coordination mechanism essentially, which may enhance the flexibility of payment scheduling and be helpful for the two parties to get more profits from the project. Through solving and analyzing an instance the insight that the bonus–penalty structure may advance the project completion effectively and improve the profits of the two parties in the meantime can be obtained.     

A deterministic particle method for the Vlasov–Fokker–Planck equation in one dimension

The Vlasov–Fokker–Planck equation is a model for a collisional, electrostatic plasma. The approximation of this equation in one spatial dimension is studied. The equation under consideration is linear in that the electric field is given as a known function that is not internally consistent with the phase space distribution function. The approximation method applied is the deterministic particle method described in Wollman and Ozizmir [Numerical approximation of the Vlasov–Poisson–Fokker–Planck system in one dimension, J. Comput. Phys. 202 (2005) 602–644]. For the present linear problem an analysis of the stability and convergence of the numerical method is carried out. In addition, computations are done that verify the convergence of the numerical solution. It is also shown that the long term asymptotics of the computed solution is in agreement with the steady state solution derived in Bouchut and Dolbeault [On long time asymptotics of the Vlasov–Fokker–Planck equation and of the Vlasov–Poisson–Fokker–Planck system with coulombic and Newtonian potentials, Differential Integral Equations 8(3) (1995) 487–514].     

A two-phase tabu search approach to the location routing problem

In many distribution systems, the location of the distribution facilities and the routing of the vehicles from these facilities are interdependent. Although this interdependence has been recognized by academics and practitioners alike, attempts to integrate these two decisions have been limited. The location routing problem (LRP), which combines the facility location and the vehicle routing decisions, is NP-hard. Due to the problem complexity, simultaneous solution methods are limited to heuristics. This paper presents a two-phase tabu search architecture for the solution of the LRP. First introduced in this paper, the two-phase approach offers a computationally efficient strategy that integrates facility location and routing decisions. This two-phase architecture makes it possible to search the solution space efficiently, thus producing good solutions without excessive computation. An extensive computational study shows that the TS algorithm achieves significant improvement over a recent effective LRP heuristic.     

Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths

Given arbitrary source and target nodes s, t and an s–t-flow defined by its flow-values on each arc of a network, we consider the problem of finding a decomposition of this flow with a minimal number of s–t-paths. This problem is issued from the engineering of telecommunications networks for which the task of implementing a routing solution consists in integrating a set of end-to-end paths. We show that this problem is NP-hard in the strong sense and give some properties of an optimal solution. We then propose upper and lower bounds for the number of paths in an optimal solution. Finally we develop two heuristics based on the properties of a special set of solutions called saturating solutions.     

A generalized optimization method for night vision devices design considering stochastic external surveillance conditions

The paper describes a generalized optimization method for night vision devices (NVDs) design taking into account stochastic external surveillance conditions – ambient light illumination, atmosphere transmittance, contrast between target and background and target type. The main idea of the presented method is optimizing of the NVD design process by optimal choice of the optoelectronic channel modules – objective, image intensifier tube, ocular and electrical battery power supply while considering the influence of the external surveillance conditions uncertainty. For that goal a stochastic nonlinear mixed-integer multicriteria optimization problem is formulated and solved. The problem solution gives the optimal modules combination and some preliminary estimation about the operational characteristics of the designed NVD – working range (consistent with the uncertainty of the external surveillance conditions), weight, price and electrical batteries power supply operational duration. An illustrative numerical example based on the optimal choice from sets of objectives, image intensifier tubes, oculars and electrical batteries types is solved. The described method increases the effectiveness of the NVD design.