NDLI: Route generation for warehouse management using fast heuristics

Content Provider	IEEE Xplore Digital Library
Author	Rubrico, J.I.U. Ota, J. Tamura, H. Akiyoshi, M. Higashi, T.
Copyright Year	2004
Description	Author affiliation: Dept. of Precision Eng., Tokyo Univ., Japan (Rubrico, J.I.U.; Ota, J.)
Abstract	In this paper, fast heuristics for a centralized multi-agent route planner are presented and computationally evaluated. We solve a sub-problem of warehouse scheduling involving the routing of intelligent agents as a preliminary step in optimizing the total schedule. The problem involves the generation of routes for automated agents tasked with the transfer of items within a warehouse from storage pallets to a common loading shed. The goal is to minimize the total distance of the routes and the number of routes generated. This constitutes a multiple-objective optimization problem which is NP-hard and hence can take a prohibitively long time to solve using existing search-based techniques. The approach adapted here is to model the system as a split delivery vehicle routing problem (SDVRP) with grid distances and to solve it using heuristics based on tested operations research concepts. Twenty-two such heuristics are tested including the well-known greedy nearest-neighbor (NN) heuristic, and the established savings heuristic of Clarke and Wright. The author introduces two SDVRP variations of the NN algorithm, namely the nearest-fill (NF) and nearest-fill farthest-start (NFFS) heuristics. Existing SDVRP improvement procedures are also considered and generalized to produce numerous heuristic variations. This novel approach of applying fast vehicle routing heuristics to multi-agent routing has the advantage of yielding good quality results within a very short period of time. The results of the study show that the greedy NFFS heuristic combined with the improvement procedures, consistently produces superior results with regard to minimization of distance and the number of routes in an the instances tested.
Starting Page	2093
Ending Page	2098
File Size	449891
Page Count	6
File Format	PDF
ISBN	0780384636
DOI	10.1109/IROS.2004.1389706
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-09-28
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Robotics and automation Routing Vehicles System testing Neural networks Robot sensing systems Peak to average power ratio Intelligent agent Operations research Noise measurement
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in