Language：English   Publishing type：Research paper (scientific journal)   Publisher：PERGAMON-ELSEVIER SCIENCE LTD  

Electric vehicles have recently received considerable attention given their environmental and financial implications. This paper focuses on electric and diesel-powered vehicle routing, a vehicle routing problem targeted at electric and diesel-powered vehicles. We introduce the new concept of original graph, where various conditions such as inclines of roads, vehicle speed and acceleration are considered. Moreover, we formulate the problem as a mixed integer linear programming formulation. The results of simulations demonstrate the utility of the new model in the real world. (C) 2017 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.tre.2017.09.004

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Japanese Operations Management and Strategy Association  

Research in the field of scheduling has been undergoing a shift in recent years from a focus on nurse scheduling to that on service industry scheduling at hotels and restaurants. Reducing employment costs and figuring out how to put non-regular employments in place to cope with fluctuating demand are critical issues in this sector, particularly when it comes to the scheduling problem to the service industry that depends on human service providers. To cope with these challenges, this paper proposes a shift scheduling model that effectively takes into consideration non-regular employments specializing in food and beverage service in hotel restaurants. It also considers the use of two types of the non-regular employments who are called monthly staff and one-time staff with different working arrangements.

DOI： 10.20586/joms.6.1_17

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE COMPUTER SOC  

Electric vehicles have recently received attention due to the environmental and financial implication. However, they are still not popular because of their inconvenience; limited battery capacities and long recharge times. In order to grow popular of electric vehicles, several studies in the field of optimization have been engaged. One of the studies is routing problem for energy-optimized driving. In this paper, we deal with the electric and fuel-engined vehicle routing problem (EFVRP); this problem is a type of the vehicle routing problem where we use electric vehicles and fuel-engined vehicles (e.g. gasoline-powered vehicles). We model the EFVRP and propose a column generation approach for the EFVRP. Experiments compare the results obtained using our model and algorithm with their lower bounds.

DOI： 10.1109/SMC.2015.346

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

A hypergraph F is a set family defined on vertex set V. The dual of F is the set of minimal subsets H of V such that F boolean AND H not equal phi for any F is an element of F. The computation of the dual is equivalent to several problems, such as minimal hitting set enumeration of a subset family, generation problem for maximal frequent and minimal infrequent sets, and so on. Although many algorithms have been proposed for the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of minimal hitting sets. In this paper, we propose efficient algorithms for checking the minimality and pruning methods. These algorithms enable us to construct time effective and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time. (C) 2014 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2014.01.012

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE Computer Society  

The multi-vehicle covering tour problem (m-CTP) is defined on a graph G = (V ∪ W, E), where V is a set of vertices that can be visited and W is a set of vertices that must be covered but cannot be visited. Each vertex in V covers a subset of W. Given the costs of edges (v&lt
inf&gt
i&lt
/inf&gt
, v&lt
inf&gt
j&lt
/inf&gt
) ε E, the objective of the m-CTP is to obtain a set of total minimum cost tours on subset of V, while covering all v&lt
inf&gt
l&lt
/inf&gt
ε W by up to m vehicles. In this paper, we propose algorithms for the m-CTP using column generation approach. Computational experiments show that our algorithms outperform the existing algorithms.

DOI： 10.1109/CoASE.2014.6899457

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：PERGAMON-ELSEVIER SCIENCE LTD  

Multi-chip module (MCM) substrates are designed for packing two or more semiconductor chips. On these substrates, there are open faults in the wiring, which are electrical disconnections. We must therefore test the substrates to detect open faults, and it is essential to establish an efficient method of testing them. One type of test method uses two probes. Two probes, each touching one edge (end) of an inter-chip wiring, are used to check for the presence of faults. Testing is complete when we have confirmed that no faults exist on the MCM substrate. The objective is to minimize the time to complete testing, that is, our aim is to design efficient routes for the two probes. In this paper, we propose a novel approach of formulating the routing problem as a shortest path problem with covering constraints (SPCC) and we also propose three algorithms for the SPCC. In computational experiments, we show that our formulation and algorithms outperform the existing method. (C) 2013 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.compeleceng.2012.12.020

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Society for Industrial and Applied Mathematics Publications  

A hypergraph F is a set family defined on vertex set V. The dual of F is the set of minimal subsets H of V such that F ∪ H ≠ for any F ∈ F. The computation of the dual is equivalent to many problems, such as minimal hitting set enumeration of a subset family, minimal set cover enumeration, and the enumeration of hypergraph transversals. In this paper, we introduce a new set system induced by the minimality condition of the hitting sets, that enables us to use efficient pruning methods. We further propose an efficient algorithm for checking the minimality, that enables us to construct time efficient and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in practical time.

DOI： 10.1137/1.9781611972931.1

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：JAPAN SOC MECHANICAL ENGINEERS  

A multi-chip module substrate is designed for packing two or more semiconductor chips. On a substrate, there may exist two types of faults; one in a wiring and the other at an intersection of two wires, called via, and the faults must be detected. The testing is performed by a pair of probes, which touch the two ends of an inter-chip wiring. The completion time of the whole testing is the time when it has been confirmed that no fault exists on the substrate. A two-probe routing problem is considered to design efficient routes of the two probes for minimizing the completion time of the whole testing. In this paper, the two-probe routing problem is formulated as a constrained shortest path problem, and a heuristic algorithm by local search techniques is proposed. Computational experiments demonstrate that the proposed heuristic algorithm outperforms a known two-phase heuristic.

DOI： 10.1299/jamdsm.7.644

Web of Science

researchmap

Publishing type：Research paper (international conference proceedings)  

DOI： 10.20586/joms.5.1_74

researchmap

Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

Printed circuit boards (PCBs) are designed for packing two or more semiconductor chips. On these PCBs, there are various types of faults in the wiring. We must therefore test the PCBs to detect these faults, and it is essential to establish an efficient testing method. One type of test method uses two probes. Two probes, each touching one edge (end) of an inter-chip wiring, are used to check for the presence of faults. Testing is complete when we have confirmed that no faults exist on the PCB. The objective is to minimize the completion time for the testing, that is, our aim is to design efficient routes for the two probes; this is a two-probe routing problem. Several previous studies have proposed an approach involving a two-phase method. Although the two-phase method quickly finds a feasible solution, there is no guarantee that the solution is good. Besides, in recent years, PCB technology provides dense assembly capability and increased chip packaging; this implies that the scale of the two-probe routing problem becomes larger and the problem is difficult to be solved. We therefore propose a new approach, where we formulate a two-probe routing problem as a combinatorial optimization problem and then, we solve the combinatorial optimization problem by using genetic algorithm. We expect that our approach is useful for solving the large-scale problems. In computational experiments, we compare the results of our approach with those obtained using the two-phase method, and we show that our approach outperforms the two-phase method.

DOI： 10.1109/CEC.2012.6253012

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

Multi-chip module (MCM) substrate is designed to pack two or more semiconductor chips. On a MCM substrate, there might exist a few types of faults in the wiring. Thus, it is essential to establish an efficient method for testing in MCM to detect faults. This paper presents a heuristic algorithm for substrates testing in MCM. Our objective is to minimize the completion time of the testing. The testing is performed by two equipments, called probe. Several previous works propose a method for the testing. Although the method finds at least one feasible solution fast, there is no guarantee that the solution is always good. Therefore, we formulate a testing problem as a shortest path problem with covering constraints (SPCC) and then, we propose a heuristic algorithm for the SPCC. In computation experiments, we show the SPCC approach are superior to the existing method.

DOI： 10.1109/IEEM.2011.6117891

Web of Science

researchmap

Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publisher：Biomedical Fuzzy Systems Association  

We examine a technique for solving the scheduling problem in the flexible flow shop, where the processing time is uncertain. The conventional scheduling method for the flexible flow shop is usually based on afirst-in-flrst-out rule at each stage. However, there is no guarantee that a good solution can be obtained by this method, especially because of the uncertain processing time. In the present study, we attempt to develop a scheduling method that provides a robust schedule against uncertainty in the processing time. In the present paper, we consider a procedure by which to generate robust schedules depending on the degree of uncertainly.

DOI： 10.24466/ijbschs.15.1_45

researchmap

Publishing type：Research paper (scientific journal)   Publisher：Japan Society of Mechanical Engineers  

DOI： 10.1299/kikaic.76.3220

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：Japan Industrial Management Association  

This paper discusses a version of the vehicle routing problem with stochastic demand (VRPSD). In this problem, a customer's demand is characterized by a known probability distribution and the customer's actual demand is only revealed when the vehicle reaches the customer location. In such a problem, two approaches are proposed. The objective of the first approach is to find a route sequence that minimizes the expected travel cost. This approach has good performance stochastically; however, when it is applied an upper bound on the travel cost cannot be guaranteed. The second approach is a robust approach implemented through chance-constrained programming. The objective is to find a route sequence that is robust with respect to uncertain demands and, at the same time, minimize the travel cost. When the probability that the vehicle's route is executed as planned is high, the route is said to be robust. In chance-constrained programming, the maximum allowable probability of route failure can be specified by the planner. The chance-constrained approach may have a higher travel cost than the first approach; however, it can guarantee a boundary for worst case performance. In this paper, we employ the chance-constrained approach as a robust method. We formulate VRPSD as a set-covering problem and solve the problem using column generation. We propose an efficient method for designing the route sequences that enable the maximum allowable probability of route failure to be specified.

DOI： 10.11221/jima.60.289

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

The vehicle routing problem with stochastic demand (VRPSD) is one of the most important problems in distribution and transportation. The classical models for the vehicle routing problem with stochastic demand are the chance-constrained model and the penalty model. This paper proposes the hybrid model which combines the chance-constrained model and the penalty model. The travel cost of the hybrid model is less than that of the chance-constrained model and the worst case is guaranteed though the hybrid model may have more travel cost than the penalty model. We formulate the VRPSD as a set covering problem and this problem is solved using a column generation approach. We propose the solution methods for the hybrid model. The solution method is based on saving algorithm. In numerical results, we compare the results of the chance-constrained model, the penalty model and the hybrid model. © 2010 Inderscience Enterprises Ltd.

DOI： 10.1504/IJAMS.2010.033566

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Publishing type：Research paper (international conference proceedings)  

researchmap

Event date： 2008.9

Language：Japanese  

researchmap

Event date： 2006.9

Language：Japanese  

researchmap

Event date： 2005

Language：Japanese  

We examine the technique for solving the scheduling problem in the flexible flow shop where processing time is uncertain. The conventional scheduling method for flexible flowshop is usually based on first out first in rule on each stage. However, there is no guarantee that a good solution can be obtained by this method, especially for the uncertain processing time. Then, in this study, we consider to express the distribution of uncertain processing time with a normal distribution. Then, we aim to develop the scheduling method which provides a robust solution to the change of the degree of uncertainty.

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap