Stacker crane problem
ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ನಲ್ಲಿ, ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಸಮಸ್ಯೆಯು ಟ್ರಾವೆಲಿಂಗ್ ಸೇಲ್ಸ್ ಪರ್ಸನ್ ಸಮಸ್ಯೆಗೆ ನಿಕಟವಾಗಿ ಸಂಬಂಧಿಸಿರುವ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಇದರ ಇನ್ಪುಟ್ ಮೆಟ್ರಿಕ್ ಜಾಗದಲ್ಲಿ ಕ್ರಮಬದ್ಧ ಜೋಡಿ ಬಿಂದುಗಳ ಸಂಗ್ರಹವನ್ನು ಒಳಗೊಂಡಿದೆ, ಮತ್ತು ಈ ಬಿಂದುಗಳನ್ನು ಕನಿಷ್ಠ ಒಟ್ಟು ಉದ್ದದ ಚಕ್ರಕ್ಕೆ ಸಂಪರ್ಕಿಸುವುದು ಗುರಿಯಾಗಿದೆ, ಅದು ಎಲ್ಲಾ ಜೋಡಿಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಪರಸ್ಪರ ಸ್ಥಿರವಾಗಿ ಆಧಾರಿತವಾಗಿದೆ. ಈ ವಿತರಣೆಗಳ ಸಮಯದ ಮೇಲೆ ನಿರ್ಬಂಧಗಳಿಲ್ಲದೆ ಸರಳೀಕೃತ ರೂಪದಲ್ಲಿ ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್, ನಿರ್ಮಾಣ ಕ್ರೇನ್ ಅಥವಾ (ಡ್ರೈಜ್ನಲ್ಲಿ) ಟ್ರಕ್ ಮೂಲಕ ಪ್ರತ್ಯೇಕ ಲೋಡ್ಗಳ ಸರಕುಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮತ್ತು ವಿತರಿಸುವ ಸಮಸ್ಯೆಗಳನ್ನು ಇದು ರೂಪಿಸುತ್ತದೆ. ಇದನ್ನು ಮಿಶ್ರ ಗ್ರಾಫ್ಗಳ ವಿಷಯದಲ್ಲಿ ಸಮಾನವಾದ ಸೂತ್ರೀಕರಣದೊಂದಿಗೆ ಪರಿಚಯಿಸಲಾಯಿತು, ನಿರ್ದೇಶನದ ಅಂಚುಗಳು ಇನ್ಪುಟ್ ಜೋಡಿಗಳನ್ನು ರೂಪಿಸುತ್ತವೆ ಮತ್ತು ನಿರ್ದೇಶನವಿಲ್ಲದ ಅಂಚುಗಳು ಅವುಗಳ ದೂರವನ್ನು ರೂಪಿಸುತ್ತವೆ. ಫ್ರೆಡೆರಿಕ್ಸನ್ ಮತ್ತು ಇತರರು. ಡೇನಿಯಲ್ ಜೆ. ರೋಸೆನ್ಕ್ರಾಂಟ್ಜ್ ಅವರ ವೈಯಕ್ತಿಕ ಸಂವಹನಕ್ಕೆ ಅದರ ಸೂತ್ರೀಕರಣವನ್ನು ಕ್ರೆಡಿಟ್ ಮಾಡಿ. ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಸಮಸ್ಯೆಯನ್ನು ಮೆಟ್ರಿಕ್ ಸ್ಥಳಗಳಲ್ಲಿ ಪ್ರಯಾಣಿಸುವ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆಯ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿ ನೋಡಬಹುದುಃ ಪ್ರಯಾಣದ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆಯ ಯಾವುದೇ ನಿದರ್ಶನವನ್ನು ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಸಮಸ್ಯೆಯ ಉದಾಹರಣೆಯಾಗಿ ಪರಿವರ್ತಿಸಬಹುದು, ಪ್ರಯಾಣದ ಮಾರಾಟಗಾರರ ನಿದರ್ಶನದಲ್ಲಿ ಪ್ರತಿ ಬಿಂದುವಿಗೆ ಒಂದು ಜೋಡಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಇನ್ನೊಂದು ದಿಕ್ಕಿನಲ್ಲಿ, ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಸಮಸ್ಯೆಯನ್ನು ಅಸಮಪಾರ್ಶ್ವದ ಪ್ರಯಾಣದ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ನೋಡಬಹುದು, ಅಲ್ಲಿ ಅಸಮಪಾರ್ಶ್ವದ ಪ್ರಯಾಣದ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆಯ ಅಂಶಗಳು ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಉದಾಹರಣೆಯ ಜೋಡಿಗಳು ಮತ್ತು ಒಂದು ಜೋಡಿಯ ಅಂತರದಿಂದ ಇನ್ನೊಂದಕ್ಕೆ ಮೊದಲ ಜೋಡಿಯ ವಿತರಣಾ ಬಿಂದುವಿನಿಂದ, ಅದರ ಪಿಕಪ್ ಬಿಂದುವಿನ ಮೂಲಕ, ಎರಡನೇ ಜೋಡಿಯ ವಿತರಣಾ ಬಿಂದುವಿಗೆ ದೂರವನ್ನು ತೆಗೆದುಕೊಳ್ಳಲಾಗುತ್ತದೆ. ಇದು ಪ್ರಯಾಣಿಸುವ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆಯನ್ನು ಸಾಮಾನ್ಯಗೊಳಿಸುವುದರಿಂದ, ಇದು ಅದೇ ಗಣನೆಯ ಸಂಕೀರ್ಣತೆಯನ್ನು ಆನುವಂಶಿಕವಾಗಿ ಪಡೆಯುತ್ತದೆಃ ಇದು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ, ಮತ್ತು ಕನಿಷ್ಠ ಅಂದಾಜು ಮಾಡಲು ಕಷ್ಟವಾಗುತ್ತದೆ. ಪ್ರಯಾಣಿಸುವ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆಗಾಗಿ ಕ್ರಿಸ್ಟೋಫೈಡ್ಸ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಆಧರಿಸಿದ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ 9/5 ರ ಅಂದಾಜು ಅನುಪಾತದೊಳಗೆ ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಸಮಸ್ಯೆಯ ಪರಿಹಾರವನ್ನು ಅಂದಾಜು ಮಾಡಬಹುದು. ಬಳಸಿದ ಒಟ್ಟು ನೂಲಿನ ಪ್ರಮಾಣವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಕಸೂತಿ ಮಾದರಿಯ ಹಿಂಭಾಗವನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸುವ ಸಮಸ್ಯೆಯು ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಸಮಸ್ಯೆಯೊಂದಿಗೆ ನಿಕಟ ಸಂಬಂಧವನ್ನು ಹೊಂದಿದೆ, ಆದರೆ ಇದು ಅದರ ಪ್ರತಿಯೊಂದು ಜೋಡಿ ಬಿಂದುಗಳನ್ನು (ಮಾದರಿಯ ಮುಂಭಾಗದಲ್ಲಿರುವ ಗೋಚರ ಹೊಲಿಗೆಗಳ ತುದಿಗಳು) ಎರಡೂ ದಿಕ್ಕುಗಳಲ್ಲಿ ಹಾದುಹೋಗಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ, ಬದಲಿಗೆ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೂಲಕ ಸ್ಥಿರವಾದ ದಿಕ್ಕಿನಲ್ಲಿ ಹಾದುಹೋಗಲು ಟ್ರಾವರ್ಸಲ್ ಅಗತ್ಯವಿರುತ್ತದೆ. ಪ್ರಯಾಣಿಸುವ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆಯಿಂದ ಅದೇ ರೂಪಾಂತರದಿಂದ ಇದು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ, ಮತ್ತು 2 ರ ಅಂದಾಜು ಅನುಪಾತದೊಳಗೆ ಅಂದಾಜು ಮಾಡಬಹುದು. ಡಯಲ್-ಎ-ರೈಡ್ ಸಮಸ್ಯೆ ಎಂದು ಕರೆಯಲಾಗುವ ಸ್ಟ್ಯಾಕರ್ ಕ್ರೇನ್ ಸಮಸ್ಯೆಯ ಮತ್ತೊಂದು ರೂಪಾಂತರವು, ವಾಹನವು ತನ್ನ ಮಾರ್ಗದಲ್ಲಿ ಯಾವುದೇ ಹಂತದಲ್ಲಿ ಕೆಲವು ಸಂಖ್ಯೆಯ ಲೋಡ್ಗಳನ್ನು ಹಿಡಿದಿಡಲು ಅನುವು ಮಾಡಿಕೊಡುವಾಗ ಪಿಕ್ಅಪ್ಗಳು ಮತ್ತು ಡೆಲಿವರಿಗಳ ಸಂಗ್ರಹವನ್ನು ನಿರ್ವಹಿಸಲು ಕನಿಷ್ಠ ಮಾರ್ಗವನ್ನು ಕೇಳುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಪ್ರಯಾಣ ಮಾರಾಟಗಾರರ ಸಮಸ್ಯೆ