A critical analysis of the “improved Clarke and Wright savings algorithm”

In their paper “An improved Clarke and Wright savings algorithm for the capacitated vehicle routing problem,” published in ScienceAsia (38, 3, 307–318, 2012), Pichpibul and Kawtummachai developed a simple stochastic extension of the well‐known Clarke and Wright savings heuristic for the capacitated vehicle routing problem. Notwithstanding the simplicity of the heuristic, which they call the “improved Clarke and Wright savings algorithm” (ICW), the reported results are among the best heuristics ever developed for this problem. Through a careful reimplementation, we demonstrate that the results published in the paper could not have been produced by the ICW heuristic. Studying the reasons how this paper could have passed the peer review process to be published in an ISI‐ranked journal, we have to conclude that the necessary conditions for a thorough examination of a typical paper in the field of optimization are generally lacking. We investigate how this can be improved and come to the conclusion that disclosing source code to reviewers should become a prerequisite for publication.     

CLSP问题的周期调度方法及其PSO求解

采用分解思想考虑多阶段CLSP问题,从多阶段生产系统抽象出单阶段生产环节,提出以周期方式对该生产环节进行生产批量调度。在对CLSP周期调度问题进行描述和界定的基础上,建立了相应的数学模型,讨论了周期调度方法中的周期上界以及周期长度与物料批量大小之间的关系等性质,采用基于三层编码的粒子群优化算法进行问题求解。源于冷轧生产实际的计算实例表明周期方法能够大大降低问题的规模且所得设备调整费用比人工方法减少约16%。     

Discussion related to “Wang,C.-H., & Lu,J.-Z. (2009). A hybrid genetic algorithm that optimizes capacitated vehicle routing problem. Expert Systems with Applications, 36(2), 2921–2936”

This paper presents a discussion arisen after reading “A hybrid genetic algorithm that optimizes capacitated vehicle routing problem”, by Wang & Lu, (Wang, C.-H., & Lu, J.-Z. (2009). A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert System with Applications, 35, 2921–2936.). The discussed paper presents a hybrid genetic algorithm applied to the Capacitated Vehicle Routing Problem (CVRP). When the authors present the results obtained by the technique, they claim to have overcome the best-known solution in two instances of Christofides and Eilon CVRP Benchmark. This statement can create confusion and controversy, for several reasons that we will explain and clarify in this short communication.     

Lower and upper bounds for a capacitated plant location problem with multicommodity flow

In this paper, we introduce a capacitated plant location problem with multicommodity flow. Given a set of potential plant sites and a set of capacitated arcs linking plants, transshipment points and customers, the aim is to determine where to locate plants and how to move flows from open plants to customers through a set of transshipment points. This model extends the classical capacitated plant location problem by introducing a multicommodity flow problem in the distribution issue. The combination of the location problem and the flow distribution problem is reasonable and realistic since both of them belong to strategic planning horizons. We propose a Lagrangean-based method, including a Lagrangean relaxation, a Lagrangean heuristic and a subgradient optimization, to provide lower and upper bounds of the model. Then, we employ a Tabu search to further improve upper bounds provided by the Lagrangean procedure. The computational results demonstrate that our solution method is effective since gaps between the upper and lower bound are on average around 2%.     

A cutting plane method for knapsack polytope

A separation algorithm for knapsack polytope is proposed. This algorithm has been used in the branch-and-cut method for solving the generalized assignment problem and the capacitated p-median problem. The computational experiment on the test instances has shown that this method is highly competitive in comparison with the existing approaches.     

Hybrid methods for lot sizing on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines, and apply Dantzig–Wolfe decomposition to a strong reformulation of the problem. Unlike in the traditional approach where the linking constraints are the capacity constraints, we use the flow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds. We solve the master problem applying two solution methods that combine Lagrangian relaxation and Dantzig–Wolfe decomposition in a hybrid form. A primal heuristic, based on transfers of production quantities, is used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the hybrid methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software.     

Solving capacitated part‐routing problems with setup times and costs: a Dantzig–Wolfe decomposition‐based solution approach

We develop a Dantzig–Wolfe decomposition‐based approach for solving the capacitated part‐routing problem with routing flexibilities, setup times, and setup costs. Large instances of the problem are solved to near‐optimality using the proposed approach. The computational performance of the approach is compared with that of the existing Lagrangean relaxation‐based approach in terms of solution quality and computational times.     

METHODOLOGY CHOICE,COMPLEXITY TEXTURE,SELF-REFLECTION

Substantial efforts have been dedicated toward the development of systems methodologies for “problem solving,” with various research groups concentrating on particular approaches. Recently, however, there have been moves toward reconciling these varying approaches within one overall framework, thus cutting out “isolationism” and inevitable ensuing sniping. This paper provides an overview of three attempts to promote such openness and conciliation (in terms of theory, methodology, and ideology), draws them together, and then demonstrates the practical importance of a critical approach through a series of contrasting applications and by reflecting on ideas from the three approaches.     

A variable neighborhood descent heuristic for arc routing problems with time-dependent service costs

This paper proposes a variable neighborhood descent heuristic for solving a capacitated arc routing problem with time-dependent service costs. The problem is motivated by winter gritting applications where the timing of each intervention is crucial. The variable neighborhood descent is based on neighborhood structures that manipulate arcs or sequences of arcs. Computational results are reported on problems derived from classical capacitated arc routing problem instances. A comparison is also provided with an alternative approach where the arc routing problem is solved after being transformed into an equivalent node routing problem.     

A variable neighborhood descent heuristic for arc routing problems with time-dependent service costs

This paper proposes a variable neighborhood descent heuristic for solving a capacitated arc routing problem with time-dependent service costs. The problem is motivated by winter gritting applications where the timing of each intervention is crucial. The variable neighborhood descent is based on neighborhood structures that manipulate arcs or sequences of arcs. Computational results are reported on problems derived from classical capacitated arc routing problem instances. A comparison is also provided with an alternative approach where the arc routing problem is solved after being transformed into an equivalent node routing problem.     

Airline network design and hub location problems

Due to the popularity of hub-and-spoke networks in the airline and telecommunication industries, there has been a growing interest in hub location problems and related routing policies. In this paper, we introduce flow-based models for designing capacitated networks and routing policies. No a priori hub-and-spoke structure is assumed. The resulting networks may suggest the presence of “hubs”, if cost efficient. The network design problem is concerned with the operation of a single airline with a fixed share of the market. We present three basic integer linear programming models, each corresponding to a different service policy. Due to the difficulty of solving (even small) instances of these problems to optimality, we propose heuristic schemes based on mathematical programming. The procedure is applied and analyzed on several test problems consisting of up to 39 U.S. cities. We provide comments and partial recommendations on the use of hubs in the resulting network structures.     

Addressing the production balancing problem

The problem of achieving a uniform flow rate through a production line and controlling in-process inventories, i.e. balancing a line, has been the subject of prior research. Much of this research has been directed at identifying “optimal” solutions to the problem. The implementation of derived techniques, however, has been ignored. Particularly, some of the behavioral factors involved with implementing a technique has been disregarded. This paper describes an approach which addresses the “balancing problem” but considers the problem of implementation. The approach specifically examines production personnel reassignments as a key implementation factor.Some prior research studies identify variable operator performance times as a key factor relating to less than uniform flow rates and excess inventories. The approach proposed in this study demonstrates that average operator performance times can be used when multiple periods are used to implement a desired solution.     

A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries

The vehicle routing problem with simultaneous pick-up and deliveries, which considers simultaneous distribution and collection of goods to/from customers, is an extension of the capacitated vehicle routing problem. There are various real cases, where fleet of vehicles originated in a depot serves customers with pick-up and deliveries from/to their locations. Increasing importance of reverse logistics activities make it necessary to determine efficient and effective vehicle routes for simultaneous pick-up and delivery activities. The vehicle routing problem with simultaneous pick-up and deliveries is also NP-hard as a capacitated vehicle routing problem and this study proposes a genetic algorithm based approach to this problem. Computational example is presented with parameter settings in order to illustrate the proposed approach. Moreover, performance of the proposed approach is evaluated by solving several test problems.     

Computational experiments with algorithms for a class of routing problems

The vehicle routing problem, a generalization of the infamous traveling salesman problem, is a well-known distribution management problem that has been the focus of much research attention. On the other hand, generalizations of arc routing problems, such as the Chinese postman problem, have been comparatively neglected. In a recent paper, we studied a class of capacitated arc routing problems from primarily a theoretical point of view. In this paper, we focus on the development and testing of algorithms for solving the capacitated Chinese postman problem. Extensive computational results are presented and analyzed.     

The problem of fair division for a hybrid resource

We propose an elementary solution to the apartment rent division problem. This problem belongs to the class of problems of “fair division,” but differs from its standard setting by “heterogeneity,” i.e., the presence of both a conventional continuous component and a discrete one, a fixed set of rooms. A combinatorial-topological approach to solving this problem in a finite number of steps (each of which requires a survey of all participants), actively used in the literature, allows to obtain an approximate decision only. We propose a fundamentally different setting, based on a priori estimates of each room by the participants and allowing, in principle, to consider various optimization tasks as well. Our approach is particularly relevant in the case of a large number of participants. We also note that the proposed approach allows to find a solution in a number of cases where the combinatorial-topological approach does not work.     

A creative thinking approach to enhancing the web-based problem solving performance of university students

Along with the advancement of information and communication technology, researchers have pointed out the necessity and challenges of developing effective instructional strategies to enhance students' web-based problem-solving performance, which refers to the ability of investigating a series of related problems via searching for, abstracting and summarizing information on the web. In this study, a creative thinking strategy is proposed to cope with this problem. Moreover, an experiment was conducted on 80 freshmen from two classes of a university to evaluate the effectiveness of the proposed approach. The experimental results show that the proposed approach improved the students' web-based problem solving performance in comparison with the conventional approach in terms of “problem finding” and “idea finding.” Moreover, it was found that the proposed approach could improve the “fact finding” performance of the students with intuitive-type cognitive style. Accordingly, some implications and suggestions are given for educators who attempt to conduct web-based problem-solving activity.     

Relationship between perceived problem‐solving skills and academic performance of novice learners in introductory programming courses

Past research has shown that student problem‐solving skills may be used to determine student final exam performance. This study reports on the relationship between student perceived problem‐solving skills 1 1 Henceforth, for brevity, we drop the word “perceived” in “student perceived problem‐solving skills” and use either “student perceived problem solving” or simply “student PSS.”
and academic performance in introductory programming, in formative and summative programming assessment tasks. We found that the more effective problem solvers achieved better final exam scores. There was no significant difference in formative assessment performances between effective and poor problem solvers. It is also possible to categorize students on the basis of problem‐solving skills, in order to exploit opportunities to improve learning around constructivist learning theory. Finally, our study identified transferability skills and the study may be extended to identify the impact of problem solving transfer skills on student problem solving for programming.     

Hierarchical representation of problem-solving knowledge in a frame-based process planning system

In most frame-based reasoning systems, the information being manipulated is represetned using frames, but the problem-solving knowledge that manipulates the frames is represented as production rules. One problem with this approach is that rules are not always a natrual way to represent knowledge; another is that systems containing lots of rules may suffer from problems with “exponetial blowup” in the amount of computation required. This paper describes a way to address these problems by organizing the problem-solving knowledge not as rules, but in a particular kind of frame hierarchy. the approach described in this paper has been implemented in a problem-solving system called SIPP (Semi-Intelligent Process Planner), which produces plans of action for the manufacture of metal parts. the paper gives an overview of SIPP, compares its knowledge representation and problem solving methods to approaches used in other knowledge-based systems, and describes goals for further research.     

Cooperation in problem solving and educational computer programs

In this article, the central issue revolves around the way cooperation between pairs of 10–12-year-old students is carried out in three problem solving contexts, one of which involves the computer. We found important differences in cooperation within these three contexts. Analyses of cooperation dialogues in these settings show that during cooperation problem solving has to take place on a content and a communication level. Cooperation requires that the cooperating subjects acquire a common frame of reference in order to be able to negotiate and communicate their individual viewpoints and inferences. These results are relevant for cooperative learning and intelligent tutoring systems. On the basis of the conclusions of this analysis a prototype of an “intelligent cooperative educational system” has been developed. Some preliminary results on cooperation with this experimental computer program are presented.     

On the use of genetic algorithms to solve location problems

This paper seeks to evaluate the performance of genetic algorithms (GA) as an alternative procedure for generating optimal or near-optimal solutions for location problems. The specific problems considered are the uncapacitated and capacitated fixed charge problems, the maximum covering problem, and competitive location models. We compare the performance of the GA-based heuristics developed against well-known heuristics from the literature, using a test base of publicly available data sets.Scope and purposeGenetic algorithms are a potentially powerful tool for solving large-scale combinatorial optimization problems. This paper explores the use of this category of algorithms for solving a wide class of location problems. The purpose is not to “prove” that these algorithms are superior to procedures currently utilized to solve location problems, but rather to identify circumstances where such methods can be useful and viable as an alternative/superior heuristic solution method.